시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 1024 MB 23 11 3 30.000%

문제

盗賊の Anna と Bruno は大富豪の邸宅に忍び込み,財宝 1 から財宝 N までの N 個の財宝を見つけた.これらの財宝を Anna と Bruno で分配することになった.財宝のうちのいくつかを Anna が取り,残りの財宝のうちのいくつかを Bruno が取る.同じ財宝を 2 人が取ることはできない.Anna や Bruno は財宝を 1 個も取らなくてもよい.また,残った財宝は邸宅に残しておくので,2 人とも取らない財宝があってもよい.

それぞれの財宝には「市場価値」と「貴重度」という 2 つの値が定まっている.Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が D 以下なら,Anna は公平だと思って満足する.一方,Bruno は,Anna より貴重度の大きい財宝が欲しいと思っている.

Anna が満足するように財宝を分配したときの,Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を求めよ.

입력

入力は 1 + N 行からなる.

1 行目には,2 つの整数 N, D (1 ≦ N ≦ 30,0 ≦ D ≦ 1015) が空白を区切りとして書かれている.これは,財宝の個数が N 個であり,Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が D 以下なら Anna が満足することを表す.

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,2 つの整数 Xi, Yi (0 ≦ Xi ≦ 1015,0 ≦ Yi ≦ 1015) が空白を区切りとして書かれている.これは,財宝 i の市場価値が Xi であり,貴重度が Yi であることを表す.

与えられる 5 つの入力データのうち,入力 1 では N ≦ 10 を満たす.また,入力 2 では D = 0 を満たす.

출력

Anna が満足するように財宝を分配したときの,Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を 1 行で出力せよ.

예제 입력

6 15
50 900
30 200
40 100
80 600
60 100
70 700

예제 출력

1200

예제 입력 2

5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0

예제 출력 2

2000000000000000

힌트

入出力例 1 においては,Anna が財宝 2 と財宝 3 と財宝 5 を取り,Bruno が財宝 1 と財宝 6 を取ると,取った財宝の市場価値の合計は Anna が 130,Bruno が 120 となり,差の絶対値 10 が D = 15 以下なので Anna は満足する.このとき,取った財宝の貴重度の合計は Anna が 400,Bruno が 1600 となり,Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値は 1200 となる.これが最大である.

※各入出力例のデータは,右クリック等によりファイルに保存して利用可能です.