当前没有测试数据。

精准价值的最小占用

题目描述

一名情报员需要将若干数据芯片藏进小盒子，每个芯片有占用体积和包含的情报价值。情报员希望芯片的总价值恰好达到目标 $V$，并使占用体积尽可能小。每个芯片只能取或不取且不可拆分；如果无法达到目标价值，输出 $-1$。

输入格式

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

接下来 $n$ 行，每行包含两个整数，表示一个芯片的体积与价值。

输出格式

输出一个整数，表示恰好达到价值 $V$ 所需的最小总占用体积；若无法达到，输出 $-1$。

输入输出样例 #1

输入 #1

4 15
3 6
5 7
4 8
6 9

输出 #1

9

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le V \le 4000$，体积与价值均在 $[1,10^4]$。EOF