問題一覧 > 通常問題

No.1858 Gorgeous Knapsack

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 72
作問者 : Shirotsume / テスター : 👑 potato167
お気に入りにしたユーザー ProblemId : 7407 / 自分の提出
問題文最終更新日: 2022-07-20 02:06:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

There are $N$ gems. The gems are numbered $1, 2, 3, \dots, N$, and gem $i$ $(1 \leq i \leq N)$ has beauty $V_i$ and weight $W_i$.

You decide to choose $0$ or more of these gems and put them in a knapsack. The capacity of the knapsack is $M$, and the total weight of the gems put in the knapsack must be at most $M$.

Here, the gorgeousness $G$ of the knapsack is defined as follows.

  • $G =$ (the minimum beauty of the gems in the knapsack) $\times$ (the sum of the beauty of the gems in the knapsack)

However, when the knapsack contains $0$ gems, its gorgeousness is $0$.

What is the maximum possible value of the gorgeousness $G$ when you choose the gems to put in the knapsack optimally?

Constraints

  • All inputs are integers
  • $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$)

Input

The input is given from Standard Input in the following format.
$N$ $M$
$V_1$ $W_1$
$V_2$ $W_2$
$\vdots$
$V_N$ $W_N$

Output

Output the maximum possible gorgeousness of the knapsack with gems put in it. End the output with a newline.

Sample

Sample 1
Input
4 30
10 8
1 6
5 11
10 3
Output
200

If you put gems $1, 4$ in the knapsack, the total weight of the gems in the knapsack is $11$, the sum of their beauty is $20$, and the minimum beauty is $10$, so the gorgeousness is $10 \times 20 = 200$.

The gorgeousness cannot be made any larger than this.

Sample 2
Input
5 25
11 11
13 3
2 7
1 3
9 7
Output
297

If you put gems $1, 2, 5$ in the knapsack, the total weight is $21$, the sum of the beauty is $33$, and the minimum beauty is $9$, so the gorgeousness is $9 \times 33 = 297$.

Sample 3
Input
5 1
100 1000
100 1000
100 1000
100 1000
100 1000
Output
0

Every gem is heavier than the capacity of the knapsack, so none can be put in. Therefore, the maximum gorgeousness is $0$.

Sample 4
Input
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
Output
1611228542126

Note that the gorgeousness may not fit in a 32-bit integer.

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