[零的突破-2011]_数发票

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

2011年在第36届ACM-ICPC国际大学生程序设计竞赛亚洲区域赛大连与成都赛站获得铜奖2项,实现了山东理工大学ACM奖牌零的突破。

 

rowanhao 手里拿着一些外出比赛的车票准备到学院报销,学院给了他一定的差旅费报销金额。而 rowanhao 平时是一个十分注重收集车票的人,他的手上有无数张不同面值的发票,现在他想计算最少要多少张发票可以恰好达到报销金额。 rowanhao 忙着整理这些发票,于是把这个任务交给了你,你需要仔细计算否则就拿不到外出的车费了。

Input

输入第一行是一个正整数 T 表示数据组数。接下来是多组数据,每组数据第一行是正整数 n ,分别表示 axuhongbo 有 n 种面值的发票(每种都有无数张),接下来一行有 n 个由空格隔开的正整数 num ,表示这 n 种面值的大小,再下一行是一个正整数 x 表示报销金额(1 <= T <= 50 , 1 <= x <= 1000 , 1 <= n <= 100 , 1 <= num <= 1000 ) 。

Output

对于每一组数据,输出能凑齐报销金额的最少的发票张数,如果不能正好凑齐则输出 -1 。

Sample Input

2
3
1 3 5
11
2
3 5
7

Sample Output

3
-1

Hint

第一组数据中 11= 5 + 5 + 1 = 5 + 3 + 3 ,最少要用 3 张。
第二组数据中无论多少张都凑不齐 7 元,输出 -1。

Source

【重聚--SDUTACM十周年庆典专场赛】axuhongbo