Candy Pink Magic Hole Flip Phone

키키가 좋아하는 Magic Hole은 $N$개의 동전 홀이 원형으로 둘러싸여 있다.

키키에게는 홀에 놓을 $N$개의 동전이 있다. 모든 동전에는 공통으로 사용되는 정수 $S$가 있으며, $i$번 동전에는 두 정수 $X_i, W_i$가 정해져 있다. 는 . 번 동전의 앞면에는 가, 뒷면에는 가 적혀 있다. 처음에는 모든 동전이 앞면을 보이고 있다.

키키는 원하는 동전을 골라 뒤집을 수 있다. 각 동전은 최대 한 번만 뒤집을 수 있으며, $i$번 동전을 뒤집으면 $W_i$점을 얻는다. 뒤집지 않은 동전은 앞면을, 뒤집은 동전은 뒷면을 보이게 된다.

뒤집을 동전을 모두 정한 뒤, 키키는 $N$개의 동전을 Magic Hole 주위의 원형 홈에 원하는 순서로 하나씩 놓는다. 원에서 서로 이웃한 두 동전에 현재 보이는 수의 합이 항상 $S$ 이상이어야 한다. 첫 번째 동전과 마지막 동전도 서로 이웃한다.

이 조건을 만족하도록 동전들을 배치할 수 있게 뒤집을 동전을 정했을 때, 얻을 수 있는 점수의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

조건을 만족하도록 동전들을 배치할 수 있게 뒤집을 동전을 정했을 때, 얻을 수 있는 점수의 최댓값을 출력한다.

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