問題一覧 > 通常問題

No.2093 Shio Ramen

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 : THE TWINSTHE TWINS / テスター : koboshikoboshi
1 ProblemId : 8589 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-07 21:02:46

問題文

太郎くんはこだわりものですが、次郎くんは食いしんぼうです。
次郎くんのテーブルには\(N\)玉の塩ラーメンが置いてあります。塩ラーメンには\(1,2, \cdots N\)と番号がついています。
各\(i\)について塩ラーメン\(i\)の塩の濃さは\(s_i\)、味の濃さは\(a_i\)です。 次郎くんは太郎くんと同じで塩ラーメンが好きで、次郎くんはできるだけ濃い味のする塩ラーメンを食べたいです。
次郎くんは大胆なので、塩ラーメンの塩がどれだけ濃くても気にしません。
ただし、次郎くんは\(I\)を超す塩の濃さの総和を含む塩ラーメンの組み合わせを食べると、病気になってしまいます。
次郎くんの友達であるあなたは、次郎くんに病気にならないような\(N\)玉の塩ラーメンの組み合わせのうち、
味の濃さの総和が最大になる組み合わせの味の濃さの総和を次郎くんに教えてあげてください。

入力

\(N\) \(I\)
\(s_1\) \(a_1\)
\(s_2\) \(a_2\)
\(\vdots\)
\(s_N\) \(a_N\)

制約
\(1 \leq N,I \leq 1000\)
\(1 \leq s_i,a_i \leq 1000\) (\(1 \leq i \leq N\))
入力はすべて整数

サンプル

サンプル1
入力
3 3
2 3
3 4
1 2
出力
5

塩ラーメン\(1\)と塩ラーメン\(3\)を選ぶことで塩の濃さの総和は\(2+1\)で\(3\)になり、味の濃さの総和は\(3+2\)で\(5\)になります。
次郎くんが病気にならずに味の濃さの総和を\(5\)より大きくすることは不可能なので\(5\)を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。