財宝 (Treasures)
日本語
Language
Contribute a translation- Time limit
- 10000 ms
- Memory limit
- 1024 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
盗賊の Anna と Bruno は大富豪の邸宅に忍び込み，財宝 \(1\) から財宝 \(N\) までの \(N\) 個の財宝を見つけた．これらの財宝を Anna と Bruno で分配することになった．財宝のうちのいくつかを Anna が取り，残りの財宝のうちのいくつかを Bruno が取る．同じ財宝を \(2\) 人が取ることはできない．Anna や Bruno は財宝を \(1\) 個も取らなくてもよい．また，残った財宝は邸宅に残しておくので，\(2\) 人とも取らない財宝があってもよい．
それぞれの財宝には「市場価値」と「貴重度」という \(2\) つの値が定まっている．Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が \(D\) 以下なら，Anna は公平だと思って満足する．一方，Bruno は，Anna より貴重度の大きい財宝が欲しいと思っている．
Anna が満足するように財宝を分配したときの，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を求めよ．
Input
入力は \(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\) を満たす．
Output
Anna が満足するように財宝を分配したときの，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を \(1\) 行で出力せよ．
Examples
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 が \(1\,600\) となり，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値は \(1\,200\) となる．これが最大である．
5 0 0 1000000000000000 0 1000000000000000 1 1 1000000000000000 0 1000000000000000 0
2000000000000000
Notes
JOI 2015 · JCIOI · CC BY-SA 4.0
Tags
No tags yet