問題一覧 > 通常問題

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

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

問題文

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

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

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

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

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

入力

入力は以下の形式で標準入力から与えられる。 
$N$ $K$
$P_1$ $D_1$
$P_2$ $D_2$
$:$
$P_N$ $D_N$
  • $1 \leq N \leq 5000$
  • $1 \leq K \leq 5000$
  • $1 \leq P_i \leq K$
  • $1 \leq D_i \leq 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もしくは右上の雲マークをクリックしてアカウントを作成してください。