No.951 [Today Only] Order One Pizza, Get Another Free!
Problem Statement
tempura went to a pizza shop.
The shop sells $N$ pizzas. The $i$-th pizza $(1 \le i \le N)$ costs $P_i$ yen and has a deliciousness of $D_i$.
The shop is currently running a free campaign. tempura can buy pizzas by repeating the following some number of times.
- Pay $P_i$ yen to buy the $i$-th pizza.
- After that, if any pizzas priced at $P_i$ yen or less remain, tempura may choose $1$ of them and buy it for free.
Find the maximum total deliciousness of the purchased pizzas when the total amount of money paid is at most $K$ yen.
Input
The input is given from standard input in the following format.$N$ $K$ $P_1$ $D_1$ $P_2$ $D_2$ $:$ $P_N$ $D_N$
- $1 \leq N \leq 5000$
- $1 \leq K \leq 5000$
- $1 \leq P_i \leq K$
- $1 \leq D_i \leq 5000$
- All input values are integers.
Output
Output on $1$ line the maximum total deliciousness of the purchased pizzas when the total amount of money paid is at most $K$ yen.
Sample
Sample 1
Input
4 5 1 1 2 10 3 1000 4 100
Output
1101
Pay $4$ yen to buy the $4$-th pizza, and buy the $3$-rd pizza for free.
Pay $1$ yen to buy the $1$-st pizza. No pizzas priced at $1$ yen or less remain, so no pizza can be bought for free.
In this case, the total amount paid is $5$ yen. The total deliciousness of the purchased pizzas is $1101$, which is the maximum.
Sample 2
Input
7 101 100 1 100 10 100 10 100 100 101 1 101 2 101 3
Output
110
Multiple pizzas with the same price or deliciousness may be sold.
Sample 3
Input
24 144 9 1856 29 3879 14 2461 44 4123 44 400 20 4447 13 4152 29 4674 30 3984 15 322 35 2646 3 4191 10 2605 6 4453 44 243 47 1854 31 3075 20 974 45 1837 4 4845 6 1673 24 2865 31 952 3 329
Output
51086
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
やむなく
りあん