#642 Dungeon Raid

Loading problem...

Preparing the statement, recent submissions, and submit form.

#642 Dungeon Raid

DOJ/Grand Contest DOJ/GCD 1/Div2

Authors: a

Time limit: 3000 ms
Memory limit: 1024 MB
Checker: DIFF
Solve threshold: 100

Statement

Statement language

Bitaro, a warrior of the Lemon Kingdom, wants to increase his level by challenging dungeons.

There are $N$ dungeons. The difficulty of dungeon $i$ is represented by two integers $A_i$ and $B_i$ . If Bitaro challenges dungeon $i$ at level $X$ , the result is as follows.

If $X \leq A_i$ , he fails and his level does not change.
If $B_i \leq X$ , he succeeds and his level increases by .

Each dungeon can be challenged at most once. Bitaro may choose the order of the dungeons and may stop at any time.

Bitaro's current level is $L$ . Find the maximum level he can reach after challenging dungeons.

Input

The input is given from Standard Input in the following format:

$N\ L$ $A_1\ B_1$ $A_{}$

Output

Print the maximum level Bitaro can reach.

Constraints

$1 \leq N \leq 500\,000$ .
$1 \leq L \leq 10^{12}$ .

Subtasks

#	Score	Constraints
1	14	$N \leq 8$ .
2	20	$N \leq 5\,000$ .
3	28	$A_i=0$ ().

Samples

Sample 1

Input

Output

By challenging dungeons $2$ , $3$ , and $1$ in this order, Bitaro's level becomes $10$ , $17$ , and $34$ , respectively.

Editorial

View editorial

2

B_{2}

A_2\ B_2