問題一覧 > 通常問題

No.951 [Today Only] Order One Pizza, Get Another Free!

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 119
作問者 : やむなく / テスター : りあん
お気に入りにしたユーザー ProblemId : 3744 / 自分の提出
問題文最終更新日: 2019-12-13 23:55:12
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
Advent Calendar Contest 2019 (順位表) の他の問題:

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.

  1. Pay $P_i$ yen to buy the $i$-th pizza.
  2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。