問題一覧 > 通常問題

No.1858 Gorgeous Knapsack

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : ShirotsumeShirotsume / テスター : potato167potato167
2 ProblemId : 7407 / 自分の提出
問題文最終更新日: 2022-07-20 02:06:43

問題文

$N$ 個の宝石があります。それぞれの宝石には $1, 2, 3, \dots, N$ の番号が付けられており、宝石 $i$ $(1 \leq i \leq N)$ の美しさは $V_i$、 重さは $W_i$ です。

あなたは、これらの宝石から $0$ 個以上選び、ナップサックに入れることにしました。ナップサックの容量は $M$ で、ナップサックに入れる宝石の重さの合計は $M$ 以下でなければいけません。

ここで、ナップサックの 豪華さ $G$ を以下のように定義します。

  • $G =$ (ナップサックに入っている宝石の美しさの最小値) $\times$ (ナップサックに入っている宝石の美しさの総和)

ただし、ナップサックに入っている宝石が $0$ 個のときの豪華さは $0$ とします。

うまくナップサックに入れる宝石を決めたとき、豪華さ $G$ の最大値はいくらになりますか?

制約

  • 入力は全て整数
  • $1 \leq N \leq 5000$
  • $1 \leq M \leq 5000$
  • $1 \leq V_i \leq 10^6$ ($1 \leq i \leq N$)
  • $1 \leq W_i \leq 5000$ ($1 \leq i \leq N$)

入力

入力は以下の形式で標準入力から与えられる。
$N$ $M$
$V_1$ $W_1$
$V_2$ $W_2$
$\vdots$
$V_N$ $W_N$

出力

ナップサックに宝石を入れたときの豪華さとして考えられる最大値を出力せよ。最後に改行すること。

サンプル

サンプル1
入力
4 30
10 8
1 6
5 11
10 3
出力
200

宝石 $1, 4$ をナップサックに入れると、ナップサックに入っている宝石の重量の総和は $11$ で、美しさの総和は $20$ 、最小値は $10$ となり、豪華さは $10 \times 20 = 200$ となります。

豪華さをこれ以上大きくすることはできません。

サンプル2
入力
5 25
11 11
13 3
2 7
1 3
9 7
出力
297

宝石 $1, 2, 5$ をナップサックに入れると、重さの総和は $21$、美しさの総和は $33$、美しさの最小値は $9$ となり、豪華さは $9 \times 33 = 297$ となります。

サンプル3
入力
5 1
100 1000
100 1000
100 1000
100 1000
100 1000
出力
0

どの宝石もナップサックの容量よりも重く、入れることができません。よって、豪華さの最大値は $0$ となります。

サンプル4
入力
25 2297
869446 1904
287909 1874
935730 2781
119975 1981
705677 929
644024 851
997269 2313
302869 939
383338 500
744220 2133
442205 1952
546991 401
792852 732
784709 539
250917 1101
922704 2274
399156 1435
844960 1077
603700 1992
276715 242
53425 691
791544 2432
949488 2471
181585 2153
329429 2118
出力
1611228542126

豪華さは32bit整数に収まらない場合があります。注意してください。

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