1362: 装箱子II
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：158
Solved：15
Description
现在小明有一个超大容量的箱子，容量为$V$,装物品只受容量限制，但是有且仅有一个。然后有n个具有容量v，价值w的物品，他想要装下物品容量和不超过箱子的容量前提下，使得总价值最大。你能帮他解决这个问题吗？请你输出这个最大值
all $0 \leq w\leq 10^5$
30分 ： $0 \leq n\leq4,0 \leq v\leq V\leq10^5$
60分 ： $0 \leq n\leq22,0 \leq v\leq V\leq10^5$
100分：$0 \leq n\leq22,0 \leq v\leq V\leq8*10^7$
all $0 \leq w\leq 10^5$
30分 ： $0 \leq n\leq4,0 \leq v\leq V\leq10^5$
60分 ： $0 \leq n\leq22,0 \leq v\leq V\leq10^5$
100分：$0 \leq n\leq22,0 \leq v\leq V\leq8*10^7$
Input
第一行一个正整数n，V
接下来n行，每行两个正整数v,w
接下来n行，每行两个正整数v,w
Output
一行，一个正整数表示最大总价值
Sample Input Copy
5 20
8 87
7 10
2 10
15 76
13 45Sample Output Copy
107