問題一覧 > 通常問題

No.1947 質より種類数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 : H20 / テスター : null 蜜蜂
21 ProblemId : 7889 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-14 21:33:47

問題文

N 種類の品物が在庫無限に存在し、i 番目の品物の値段は vi 円、価値は wi です。

DHMOさんは V 円所持しており、満足度が一番高くなるように購入します。

DHMOさんは価値の高い同じ種類の品物をたくさん買うよりも、様々な種類の品物を買う方が満足する派です。

満足度は、購入した品物の種類数に C を掛けた値と、購入した品物の価値の合計の合算になります。

支払うお金の合計を V 円以下にしたときの、満足度の最大値を答えてください。

入力

N V C
v1 w1
v2 w2
⋮
vN wN

制約

  • 1≤N,V,C≤5000
  • 1≤vi≤5000
  • 1≤wi≤5000
  • 入力は全て整数

出力

支払うお金の合計を V 円以下にしたときの、満足度の最大値を出力してください。

最後に改行してください。

サンプル

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

1 番目の品物を 1 個、2 番目の品物を 1 個、3 番目の品物を 3 個買います。

支払うお金の合計は 15 円で価値の合計は 18です。

3 種類の品物を購入したので満足度は 3×3+18 で 27 となり、この購入方法が一番満足度が高いです。

サンプル2
入力
3 13 2
3 4
5 5
3 4
出力
20

1 番目の品物を 2 個、3 番目の品物を 2 個買うと一番満足度が高いです。

同じ金額で同じ価値のものが複数存在することや、所持金額ちょうどになるように購入しなくてもよいことに気をつけてください。

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

3 番目の品物を 4 個買うと一番満足度が高いです。

購入した品物は 1 種類だけの購入ですが、一番満足度が高くなりました。

サンプル4
入力
1 1 1
1000 1
出力
0

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