問題一覧 > 通常問題

No.951 【本日限定】１枚頼むともう１枚無料！

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 111
作問者 : やむなく / テスター : りあん
24 ProblemId : 3744 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-13 23:55:12

問題文

tempura さんはピザ屋さんに行きました。

ピザ屋さんには N 枚のピザが売られています。 i 番目のピザ (1≤i≤N) の価格は Pi 円で、美味しさは Di です。

いま、このピザ屋さんでは無料キャンペーンが行われています。tempura さんは以下を何回か繰り返してピザを購入することができます。

  1. Pi 円を払って i 番目のピザを買う。
  2. その後、価格が Pi 円以下のピザが残っているならば、そのうちの 1 枚を選んで無料で買うことができる。

支払うお金の合計を K 円以下にしたときの、購入したピザの美味しさの合計の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
N K
P1 D1
P2 D2
:
PN DN
  • 1≤N≤5000
  • 1≤K≤5000
  • 1≤Pi≤K
  • 1≤Di≤5000
  • 入力はすべて整数である。

出力

支払うお金の合計を K 円以下にしたときの、購入したピザの美味しさの合計の最大値を 1 行で出力せよ。

サンプル

サンプル1
入力
4 5
1 1
2 10
3 1000
4 100
出力
1101

4 円を支払って 4 番目のピザを買い、3 番目のピザを無料で買います。

1 円を支払って 1 番目のピザを買います。価格が 1 円以下のピザは残っていないので、ピザを無料で買うことはできません。

このとき、支払ったお金の合計は 5 円です。購入したピザの美味しさの合計は 1101 となり、これが最大です。

サンプル2
入力
7 101
100 1
100 10
100 10
100 100
101 1
101 2
101 3
出力
110

価格や美味しさが同じピザが複数枚売られていることがあります。

サンプル3
入力
24 144
9 1856
29 3879
14 2461
44 4123
44 400
20 4447
13 4152
29 4674
30 3984
15 322
35 2646
3 4191
10 2605
6 4453
44 243
47 1854
31 3075
20 974
45 1837
4 4845
6 1673
24 2865
31 952
3 329
出力
51086

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