g6-07959. 大容量省内存 未做

小杨有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$，背包容量为 $V$，每件物品至多选一次，求最大总价值。注意 $V$ 最大可达 $10^7$，开整张二维表格会超出内存，请只开一行容量大小的表格来计算；部分物品的重量可能超过 $V$。

第一行两个整数 $n,V$。

接下来 $n$ 行，每行两个整数 $w_i,v_i$。

一行一个整数，表示最大总价值。

输入 1

3 10000000
6000000 100
5000000 100
5000000 100

输出 1

200

$1\le n\le 20$，$1\le V\le 10^7$，$1\le w_i\le 10^7$，$1\le v_i\le 10^4$。