No.1947 Variety over Quality
H20
null
蜜蜂Problem Statement
There are $N$ types of items with unlimited stock. The $i$-th item costs $v_i$ yen and has a value of $w_i$.
DHMO has $V$ yen and makes purchases so that the satisfaction is maximized.
DHMO is the type of person who is more satisfied by buying various types of items than by buying many items of the same high-value type.
The satisfaction is the sum of the number of types of items purchased multiplied by $C$ and the total value of the purchased items.
Find the maximum satisfaction when the total amount of money paid is at most $V$ yen.
Input
$N\ V\ C$ $v_1$ $w_1$ $v_2$ $w_2$ $\vdots$ $v_N$ $w_N$
Constraints
- $1 \le N,V,C \le 5000$
- $1 \le v_i \le 5000$
- $1 \le w_i \le 5000$
- All inputs are integers.
Output
Output the maximum satisfaction when the total amount of money paid is at most $V$ yen.
Print a newline at the end.
Sample
Sample 1
Input
4 15 3 4 5 2 1 3 4 15 20
Output
27
Buy $1$ of the $1$-st item, $1$ of the $2$-nd item, and $3$ of the $3$-rd item.
The total amount paid is $15$ yen and the total value is $18$.
Since $3$ types of items were purchased, the satisfaction is $3\times3+18$, which is $27$, and this way of purchasing gives the highest satisfaction.
Sample 2
Input
3 13 2 3 4 5 5 3 4
Output
20
Buying $2$ of the $1$-st item and $2$ of the $3$-rd item gives the highest satisfaction.
Note that multiple items may have the same price and the same value, and that you do not have to spend exactly the amount of money you have.
Sample 3
Input
3 20 1 3 4 2 3 5 9
Output
37
Buying $4$ of the $3$-rd item gives the highest satisfaction.
Only $1$ type of item was purchased, but this gave the highest satisfaction.
Sample 4
Input
1 1 1 1000 1
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。