最少硬币问题

题目描述

设有 $n$ 种不同面值的硬币，各硬币的面值为 $t_i$。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数为 $c_i$。

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

输入格式

第一行中只有 $1$ 个整数给出 $n$ 的值;

第 $2$ 行起，每行 $2$ 个数，分别是 $t_i$ 和 $c_i$。

最后 $1$ 行是要找的钱数 $m$ 。

输出格式

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

样例 #1

样例输入 #1

3

1 3

2 3

5 3

18

样例输出 #1

5

提示

$1\leq n \leq 10$，$0 \leq m \leq 20001$。