题目描述

设有$\red{n }$种不同面值的硬币，各硬币的面值存于数组$\red{T［1:n］}$中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组$\red{Coins［1:n］}$中。对任意钱数$\red{0≤m≤20001}$，设计一个用最少硬币找钱$\red{m}$的方法。 编程任务：对于给定的$\red{1≤n≤10}$，硬币面值数组$\red{T}$和可以使用的各种面值的硬币个数数组$\red{Coins}$，以及钱数$\red{m}$，$\red{0≤m≤20001}$，编程计算找钱$\red{m}$的最少硬币数。

输入格式

文件的第一行中只有$\red{1}$个整数给出$\red{n}$的值,第$\red{2}$ 行起每行$\red{2}$个数，分别是$\red{T[j]}$和$\red{Coins[j]}$。最后$\red{1}$ 行是要找的钱数$\red{m}$。

输出格式

程序运行结束时，计算出最少硬币数。问题无解时输出$\red{-1}$。

样例

输入样例

3
1 3
2 3
5 3
18

输出样例

5