1726: 疯狂珠宝店
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：15
解决：6
题目描述
又到了一年一度的ACM犒劳季节了，MOM珠宝店为表彰各位ACMer在暑期专题训练中的辛勤劳动，特地允许ACMer在珠宝店免费疯狂购物。不过此次购物也是有规则的，首先ACMer会得到一辆容量为c的疯狂购物车，他们只能最多把购物车装满，不能再私藏其它的珠宝了。不过ACMer是贪婪的，他们很快就记住了超市中每一件珠宝的体积vol和价值value，现在需要你帮忙写一个程序，让他们能够疯狂购物到最大价值总和的珠宝。
输入
输入第一行为一个整数c代表购物车的容量(1<=c<=10000)
接下来的若干行，每行有2个整数vol(<=100)和value(<=1000000)，代表了一件商品的体积和价值。MOM超市的珠宝类别数不超过100种。注意，珠宝体积虽小，价值可不菲哦！
输出
输出为一个整数，代表ACMer能够疯狂购物到的最大珠宝价值总和与20090731的余数。
样例输入 复制
11
2 4
3 7
6 5
5 8
4 6样例输出 复制
25