g6-07983. 值域倒置·模板 未做

小杨有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$，每件物品至多选一次。背包容量 $V$ 可能非常大，最大可达 $10^9$，但所有物品的价值总和很小。求在总重量不超过 $V$ 时能获得的最大总价值。

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

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

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

输入 1

4 10
5 4
4 3
6 5
3 2

输出 1

8

选第 2、3 件：价值 $3+5=8$，重量 $4+6=10\le 10$。

$1\le n\le 100$，$1\le V\le 10^9$，$1\le w_i\le 10^9$，$1\le v_i\le 100$。