题目描述

有 $n$ 种物品，每种物品有无数件，已知第 $i$ 件物品的体积为 $c_i$，价值为 $w_i$。

现在要选择一些物品放入一个容量为 $V$ 的背包，要求在背包 恰好填满（即物品体积之和等于 $V$）的前提下，放入背包中的物品的价值之和尽可能地小。

求最小价值。

输入格式

输入的第一行包含两个整数 $n$ 和 $V$，以一个空格分隔，分别表示物品种类数即背包容量。（$1 \le n \le 1000, 1 \le V \le 10^5$）
接下来 $n$ 行，每行包含两个整数，以一个空格分隔，其中第 $i$ 行包含两个整数 $c_i$ 和 $w_i$，分别表示第 $i$ 件物品的体积和价值（$1 \le c_i,w_i \le 1000$）。

输出格式

如果没有办法让放入背包的物品体积之和恰好等于 $V$，输出 “No Solution!”；
否则，输出一个整数，表示所有放入背包的物品体积之和等于 $V$ 的方案中对应的价值之和的最小值。

样例

3 10
2 3
3 4
5 9

14

3 10
3 5
6 8
8 9

No Solution!