j02049. 登山负重 未做

登山队要背总重不少于 $W$ 的装备上山。共 $n$ 件装备，第 $i$ 件重 $w_i$、实用价值 $v_i$，每件最多带一次。求带走的装备总重 $\ge$$W$ 时实用价值总和的最大值。数据保证全部装备总重 $\ge$$W$。

第一行两个整数 $n$, $W$；接下来 $n$ 行每行 $w_i$, $v_i$。

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

• 对于 30% 的数据，$n$ $\le$ 20 且 $w_i$ $\le$ 1000（子集枚举可过）。
• 对于 60% 的数据，$n$ $\le$ 100 且 $W$ $\le$ 2000。
• 对于 100% 的数据，1 $\le$ $n$ $\le$ 300，1 $\le$ $w_i$ $\le$ 10${}^4$（可超过 $W$），1 $\le$ $v_i$ $\le$ 10${}^9$，1 $\le$ $W$ $\le$ 5000。