g6-07960. 一维综合 未做

小杨有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$，背包容量为 $V$，每件物品至多选一次，总重量不能超过 $V$，求最大总价值。价值可达 $10^9$、物品最多 $100$ 件，答案请用 $64$ 位整数。

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

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

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

输入 1

2 100
50 1000000000
51 1000000001

输出 1

1000000001

第 2 件重 51 不超过容量 100，单件价值更高。

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