#L. 逆向 01 背包

传统题

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定 $n$ 个物品，每个物品有一个价值 $w_i$ 和一个体积 $v_i$ 。选择其中的一些物品，使得它们的体积之和不小于 $m$ 并且总价值最小。

$n+1$ 行。

第一行，两个整数 $n$ 和 $m$ 。

接着 $n$ 行，每行两个整数 $w_i$ 和 $v_i$ ，表示第 $i$ 个物品的价值和体积。

一行一个整数表示最小的总价值。

对于 $30\%$ 的数据， $1 \le n \le 25$ ， $1 \le m \le 100$ ， $1 \le v_i,w_i \le 100$ 。

对于 $100\%$ 的数据， $1 \le n \le 1000$ ， $1 \le m \le 10^4$ ， $1 \le v_i,w_i \le 1000$ 。