時間制限:$2.0sec$ / メモリ制限:$256MB$
盗賊の 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 ≦ 10^{15})$ が空白を区切りとして書かれている．これは，財宝の個数が N 個であり，Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が $D$ 以下なら Anna が満足することを表す．
続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，2 つの整数 $Xi, Yi (0 ≦ Xi ≦ 10^{15}，0 ≦ Yi ≦ 10^{15})$ が空白を区切りとして書かれている．これは，財宝 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
入出力例 1 においては，Anna が財宝 2 と財宝 3 と財宝 5 を取り，Bruno が財宝 1 と財宝 6 を取ると，取った財宝の市場価値の合計は Anna が 130，Bruno が 120 となり，差の絶対値 10 が D = 15 以下なので Anna は満足する．このとき，取った財宝の貴重度の合計は Anna が 400，Bruno が 1600 となり，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値は 1200 となる．これが最大である．
5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0
2000000000000000
単純な解法として，財宝の分配の仕方をすべて試すという方法が考えられる．各財宝について，「Anna が取る」「Bruno が取る」「2 人とも取らない」の 3 通りのいずれであるかを定めれば分配が決まる．しかし，分配の仕方は $3^N$ 通りとなるため，この方法は N が小さいデータに対してのみ短時間で答えを求めることができる ($3^{30} ≒ 2 × 10^{14}$ である)．
重要なアイデアは，全体の半分の財宝の分配の仕方 (最大 315 通り) をすべて試すことは比較的短時間で可能だということである．財宝全体をおよそ N/2 個ずつの 2 つの集合 S, T に分け，S, T それぞれの中での分配の仕方をすべて列挙する．ここで，各分配の仕方について，2 人が取る財宝の市場価値の合計の差と貴重度の合計の差のみを記録しておけばよいことに注意せよ．S の分配の仕方における市場価値の合計の差と貴重度の合計の差の組を (a1, b1), (a2, b2), ..., (aP, bP) とし (つまり，i 番目の分配の仕方では，Bruno が取る財宝の市場価値の合計から Anna のそれを引くと ai で，Bruno が取る財宝の貴重度の合計から Anna のそれを引くと bi である)，同様に，T の分配の仕方における市場価値の合計の差と貴重度の合計の差の組を (c1, d1), (c2, d2), ..., (cQ, dQ) とする．すると S の i 番目の分配の仕方と T の j 番目の分配の仕方を合わせたとき，市場価値の合計の差は ai + cj，貴重度の合計の差は bi + dj であるから，|ai + cj| ≦ D となるような (i, j) に対する bi + dj の最大値が本問の答えとなる．
D = 0 の場合，cj = -ai でなければならないので，i を 1 つ決めると cj の値が定まる．よって，cj の値から dj としてありうる最大値への対応を (ハッシュテーブルなどを用いて) 管理しておく，といった方法で解くことができる．
一般の場合，cj の値の範囲が指定されて dj の最大値を求めることになる．そこでまず (a1, b1), (a2, b2), ..., (aP, bP) を ai の昇順に，(c1, d1), (c2, d2), ..., (cQ, dQ) を cj の昇順にソートしよう．i を 1 つ決めると，条件は |ai + cj| ≦ D すなわち -ai - D ≦ cj ≦ -ai + D となる．これを満たす j は L(i) ≦ j ≦ R(i) のように書ける．ここで，L(1) ≧ L(2) ≧ ... ≧ L(P)，R(1) ≧ R(2) ≧ ... ≧ R(P) が成り立ち，範囲 L(i) ≦ j ≦ R(i) を左に伸ばして右から縮めると範囲 L(i + 1) ≦ j ≦ R(i + 1) が得られる．したがって，「値を 1 つ追加する」「値を 1 つ削除する」「最大値を答える」という操作を行えるデータ構造を用意すれば，i = 1, 2, ..., P の順に L(i) ≦ j ≦ R(i) の範囲での dj の最大値を求めることができる．例えば，最大値の取得が可能な平衡二分木 (C++ の std::multiset など) を用いれば各操作を O(log Q) 時間で行える．その他，両端キューを利用することで各操作をならし O(1) 時間で行う解法もある．
P, Q が 3N/2 程度のとき log P, log Q は O(N) なので，全体の時間計算量は $O(3^{N/2} N)$ となる．