#M. *L8游戏卡

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有n种游戏卡，每一种游戏卡都有一个固定的点数，假设每种游戏卡的数量都足够多，请问恰好凑出m点最少需要多少张游戏卡？

例如：n=3，3种游戏卡的点数分别为：2，5，9；m=12，恰好凑出12点的最优方案为｛5，5，2｝，最少需要3张游戏卡。

第一行包含一个整数n，表示游戏卡的种类；第二行包含n个不同的整数x₁，x₂,x₃,..., x_n,分别表示每种游戏卡的点数，整数之间以一个空格隔开；第三行包含一个整数m，表示要凑的点数。

数据范围：测试点1~10：1<=n<=10³,1<=x_i<=10³,1<=m<=10⁵。

一个整数，表示恰好凑出m点最少需要多少张游戏卡。如果无法凑出，则输出-1。

3
2 5 9
12

2
3 5
4

-1

1s, 1024KiB for each test case.