题目描述

给定一个整数和可以兑换的硬币面额，计算凑成总金额所需的最少的硬币个数。

输入格式

第一行一个整数n(1<=n<=12)，表示可兑换的硬币面额有多少种。
第二行n个整数，表示可兑换的n种硬币的面额。
第三行一个整数z表示要兑换的总金额。

输出格式

输出只有一行，包括1个整数，表示最少需要多少个硬币，如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

样例数据

input

3
1 2 5
11

output

3