圣杯修复

题目描述

在一座古老的小镇上，有一尊受损的神圣圣杯。作为一名手艺高超的工匠，你被委以重任，需要修复圣杯底座。

经测量，修复底座需要恰好 $W$ 克的金属。镇上的铁匠铺里存有 $N$ 种金属合金，每种合金的数量都是无限的。第 $i$ 种合金每块的重量为 $w_i$ 克，其价格为 $c_i$ 金币。

为了帮助小镇节省开支，你需要在保证总重量恰好为 $W$ 的前提下，计算出最少需要花费多少金币。

如果无论如何组合都无法凑齐恰好 $W$ 克的重量，请输出 "No solution"。

输入格式

第一行包含两个整数 $N$ 和 $W$，分别表示合金的种类数和需要的总重量。

接下来的 $N$ 行，每行包含两个整数 $w_i$ 和 $c_i$，分别表示第 $i$ 种合金的重量和价格。

输出格式

输出一个整数或字符串。如果能凑齐重量，输出最少的金币花费；否则输出 "No solution"。

输入输出样例 #1

输入 #1

3 10
2 5
3 8
5 12

输出 #1

24

样例 1 说明

选择两块重量为 5 的合金，总重量为 10，总代价为 $12 \times 2 = 24$。 （如果选两块重量为 2 和两块重量为 3，总重也是 10，但代价为 $5 \times 2 + 8 \times 2 = 26$，不是最优。）

输入输出样例 #2

输入 #2

2 7
4 10
6 15

输出 #2

No solution

数据范围

对于 $60\%$ 的数据，$1 \le N, W \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 10^3$，$1 \le W \le 10^4$，$1 \le w_i \le W$，$1 \le c_i \le 10^6$。

建议

二刷