/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点： 100 点
問題
盗賊の 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 \leqq N \leqq 30，0 \leqq D \leqq 10^{15}) が空白を区切りとして書かれている．これは，財宝の個数が N 個であり，Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が D 以下なら Anna が満足することを表す．
続く N 行のうちの i 行目 (1 \leqq i \leqq N) には，2 つの整数 X_i, Y_i (0 \leqq X_i \leqq 10^{15}，0 \leqq Y_i \leqq 10^{15}) が空白を区切りとして書かれている．これは，財宝 i の市場価値が X_i であり，貴重度が Y_i であることを表す．
与えられる 5 つの入力データのうち，入力 1 では N \leqq 10 を満たす．また，入力 2 では D = 0 を満たす．
出力
Anna が満足するように財宝を分配したときの，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を 1 行で出力せよ．
入力例 1
6 15 50 900 30 200 40 100 80 600 60 100 70 700
出力例 1
1200
入出力例 1 においては，Anna が財宝 2 と財宝 3 と財宝 5 を取り，Bruno が財宝 1 と財宝 6 を取ると，取った財宝の市場価値の合計は Anna が 130，Bruno が 120 となり，差の絶対値 10 が D = 15 以下なので Anna は満足する．このとき，取った財宝の貴重度の合計は Anna が 400，Bruno が 1\,600 となり，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値は 1\,200 となる．これが最大である．
入力例 2
5 0 0 1000000000000000 0 1000000000000000 1 1 1000000000000000 0 1000000000000000 0
出力例 2
2000000000000000