← 返回题目列表

AtCoder · arc042_c

C. 小吃

中文机器翻译题面 查看原题

問題文

高桥君正在选择外出旅行时携带的零食。 本次行程共包括 P 零食最多可携带100日元。 不过,我的班主任 Kensho 非常友善,所以我 1 即使有一份零食,总共也会 P 如果低于日元,他们会原谅。

例如,100 当你能带上日元时,价格就不同了。 30 円、40 円、50 如果你带了日元零食, 1 即使您删除一份零食,总数仍保留 100 他们会原谅我,因为它会低于日元。 然而,40 円、50 円、60如果你带了日元零食,40 即使没有日元零食,总共也是 110 变成日元 100 既然超过了日元,就算是好心的老师也不会允许的。

高桥君要带什么零食? N 有不同的类型,每种类型都有自己的价格和满意度。 高桥君表示,对于每种零食来说,最大 1 我只在短途旅行时携带它。 在选择Kensho老师允许的零食时,求总满意度,使总满意度最高。


入力

输入是按以下格式从标准输入给出的。

N P
a_1 b_1
a_2 b_2
:
a_N b_N
  • 1 第二行显示高桥君想要携带的零食类型以及他可以携带的零食总量。 在 2 整数 N, P (1 ≦ N ≦ 5,000, 1 ≦ P ≦ 5,000) 用空格分隔。
  • 2 从线 N 行中,有代表高桥君想要带来的每种零食的价格和满意度的整数。 如果正确答案是满足 a_i b_i (1 ≦ a_i ≦ 100, 1 ≦ b_i ≦ 100) 用空格分隔。

部分点

针对此问题设置了部分分数。 满足

  • 1 ≦ N ≦ 100, 1 ≦ P ≦ 100 的数据集 50 点。

出力

在 Kensho 老师允许的选择零食的方式中,在选择总满意度最高的零食时计算总满意度。 1 行输出。 由于字符串以


入力例1

4 100
30 50
40 40
50 100
60 80

出力例1

190

1 眼睛和 2 眼睛和 3 当您选择第二种零食时,总满意度会增加。 190 ,这是Kensho老师允许的最大选择。


入力例2

5 100
40 10
30 50
60 80
20 40
20 70

出力例2

200

入力例3

10 654
76 54
62 19
8 5
29 75
28 4
76 16
96 24
79 30
20 64
23 56

出力例3

347

该输入不包含在部分点中。