【问题描述】
小 Q 现在遇到了一道完全背包模板题，可是他不会做，请你帮帮他。
现有 n 件物品，每种物品有无限个，每种物品有一定的重量 wi 和价值 vi。问你在选择的物品的重量之和小于或等于 W 的情况下最大的价值和为多少。
【输入格式】
第一行两个整数，n 和 W。
接下来 n 行，每行两个正整数，第 i 个物品的重量 wi 和价值 vi。
【输出格式】
一行一个非负整数，表示最大的价值和。
【输入样例1】
1 10
3 2
【输出样例1】
6
【输入样例2】
5 10
1 1
2 2
3 3
4 4
5 5
【输出样例2】
10
【输入样例3】
5 10
1 1
2 3
3 3
4 8
5 7
【输出样例3】
19
【数据范围与约定】
对于 20％ 的数据，1≤n≤1000，1≤W≤1000
对于 30％ 的数据，1≤W≤10000
对于 45％ 的数据，1≤n≤10000
对于 100％ 的数据，1≤n≤1000000，1≤W≤1010，1≤wi≤100，1≤vi≤108
