問題文
高桥君正在选择外出旅行时携带的零食。 本次行程共包括 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
该输入不包含在部分点中。