题目描述

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

输入格式

$n+1$ 行。

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

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

输出格式

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

6 20
15 5
20 100
5 4
17 3
4 1
19 12

4

4 1
6 9
2 5
1 7
4 3

3

数据范围

对于 $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$。