Description

话说月光家里有许多玩具，最近他又看上了DK新买的“擎天柱”，就想用自己的跟DK的换。每种玩具都有特定的价格，价格为整数。只有月光拿出的玩具的总价格与“擎天柱”的价格相等才能换得“擎天柱”。同时，月光还希望能用最少的玩具数换回“擎天柱”。请问，月光能顺利得到梦寐以求的“擎天柱”吗？

Input

输入数据包含多组； 对于每组数据，第一行为一个正整数n(1 ≤n≤10); 表示月光手头有n个玩具。 接下来一行有n个正整数P1，P2，……，Pn（1 ≤ Pi ≤ 1000），Pi为第i个玩具的所对应的价格。 最后一行为一个正整数m(1 ≤ m ≤10000)，为“擎天柱”的价格。

Output

对于每组数据，如果能换得“擎天柱”则输出最少玩具数；否则，输出“-1”。

Sample

Input

3
1 2 3
4
4
4 3 3 5
2

Output

2
-1

Source: cryboy