#749 candypinkmagicholeflipflop

Statement

Statement language

Kiki's favorite Magic Hole consists of $N$ coin slots arranged in a circle.

Kiki has $N$ coins to place in the slots. All coins share an integer $S$ , and coin $i$ has two integers $X_i$ and $W_i$ . The values are . The front of coin shows , and its back shows . Initially, every coin shows its front.

Kiki may choose any coins to flip. Each coin may be flipped at most once, and flipping coin $i$ earns $W_i$ points. Unflipped coins show their fronts, while flipped coins show their backs.

After deciding which coins to flip, Kiki places the $N$ coins into the circular slots of Magic Hole in any order. For every pair of neighboring coins in the circle, the sum of their currently visible numbers must be at least $S$ . The first and last coins are also neighbors.

Find the maximum total score obtainable by choosing coins to flip so that they can be arranged to satisfy this condition.

Input

The input is given in the following format:

$N\ S$ $X_1\ W_1$ $_{}$

Output

Print the maximum score obtainable by choosing coins to flip while allowing a valid circular arrangement.

Constraints

$2 \le N \le 300\,000$ .
$2N \le S \le 10^9$ .

Subtasks

#	Score	Constraints
1	100	No additional constraints.

Samples

Sample 1

Input

4
10
5

Output

5

Flipping only coin $2$ makes the visible numbers $3$ and $2$ , satisfying the condition and earning $5$ points.

Sample 2

Input

Output

27

Sample 3

Input

Output

121