No.1858 Gorgeous Knapsack
タグ : / 解いたユーザー数 72
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。