#p4346. 习题7.4.9 最少硬币问题

习题7.4.9 最少硬币问题

最少硬币问题

题目描述

设有 nn 种不同面值的硬币,各硬币的面值为 tit_i。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数为 cic_i。

对任意钱数 mm ,设计一个用最少硬币找钱 mm 的方法。编程计算找钱 mm 的最少硬币数。

输入格式

第一行中只有 11 个整数给出 nn 的值;

第 22 行起,每行 22 个数,分别是 tit_i 和 cic_i。

最后 11 行是要找的钱数 mm 。

输出格式

将计算出的最少硬币数输出,问题无解时输出 −1-1 。

样例 #1

样例输入 #1


3

1 3

2 3

5 3

18

样例输出 #1


5

提示

1≤n≤101\leq n \leq 10,0≤m≤200010 \leq m \leq 20001。