2167: 零钱兑换

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：21 Solved：1

Description

给定一个数组coins，长度为n，其中coins[i]表示第i种硬币的面值，每种硬币的数量都无限。再给定一个整数amount，表示总金额。编写一个程序来计算并输出可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，输出-1。




Input

输入三行；
第一行输入正整数n，表示硬币种类的总数，n不超200；
第二行是若干个用空格隔开的不大于1000的正整数；
第三行是一个正整数amount（不大于10000）。




Output

输出一行，最少的硬币个数或-1





Sample Input Copy 

3
1 2 5
13

Sample Output Copy 

4