道具商店
题目描述
道具商店里有n件道具可供挑选 。第 i 件道具可为玩家提升 ai 点攻击力 ,需要 ci 枚金币才能购买 ,每件道具只能购买一次 。现在你有k枚金币 ,请问你最多可以提升多少点攻击力?
输入格式
第一行 ,两个正整数 n, k ,表示道具数量以及你所拥有的金币数量。
接下来 n行 ,每行两个正整数 ai , ci ,表⽰道具所提升的攻击力点数, 以及购买所需的金币数量。
输出格式
输出一行,一个整数 ,表示最多可以提升的攻击力点数。
输入样例 1
3 5
99 1
33 2
11 3
输出样例 1
132
输入样例 2
1 4 100
2 10 1
3 20 11
4 40 33
5 100 99
输出样例 2
110
数据范围
对于 60 的测试点,保证 1 ≤ k ≤ 500,1 ≤ ci ≤ 500 。
对于所有测试点,保证 1 ≤ n ≤ 500,1≤ k ≤ 109 ,1≤ ai ≤ 500, 1≤ ci ≤ 109。