8347: 大容量背包问题
[Creator : ]
Description
有 N 件物品和一个容量为 W 的背包。
第 i 件物品的重量是 w[i]，价值是 c[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
第 i 件物品的重量是 w[i]，价值是 c[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
Input
第一行为 $N\ (1≤N≤40)\ W\ (1≤V≤10^{15})$。
下面 N 行，第 i 行描述第 i 个物品的 $w_i\ (1≤w_i≤10^{15}),\ v_i\ (1≤v_i≤10^{15})$，用一个空格分隔。
下面 N 行，第 i 行描述第 i 个物品的 $w_i\ (1≤w_i≤10^{15}),\ v_i\ (1≤v_i≤10^{15})$，用一个空格分隔。
Output
输出只有一个数，最大总价值。
Sample 1 Input
3 225274242
70498827 830583485
72910089 759360759
80945586 1095298545
Sample 1 Output
2685242789