题目描述

有 $n$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $w[i]$ ，价值是 $v[i]$ 。每种物品仅有一件，可以选择放（ $1$ ）或不放（ $0$ ）。求解将哪些物品装入背包可使总容量大于等于 $V$ 且价值最小。

输入格式

输入第一行，两个整数 $n$ 和 $V$ ，分别表示一共有多少件物品和背包的容量。

接下去 $n$ 行，每行两个整数 $w_i，v_i$，分别表示物品的体积和价值。

输出格式

输出一行，装入背包可使总容量大于等于 $V$ 且价值最小。如果都没有满足条件，输出 0 。

输入输出样例

3 10
3 3
9 9
2 2

11

提示

$1 \le n \le 30，1 \le V \le 300$