No submission language available for this problem.

题目描述

假设你是一名游戏开发者，你正在设计一个游戏中的关卡。在这个关卡中，玩家需要通过收集特定的道具来达到目标得分 $M$ 。你有 $N$ 个道具，其中每个道具都会有一个得分。你需要编写一个程序，算出玩家最少需要收集多少个道具才能刚好达到目标得分。如果已有的道具，任意组合均无法达到目标得分，则输出 $-1$。

输入格式

第一行一个整数 $N$，表示会有 $N$ 个数字 $N \le 500$ 道具

第二行 $N$ 个正整数，表示道具分数，每个数 不超过 $100$

第三行一个整数 $M$ 表示目标分数值， $M<= 50000$。

输出格式

一个整数表示总数，若无法组合输出 $-1$

样例 #1

样例输入 #1

3
1 2 5
11

样例输出 #1

3

样例 #2

样例输入 #2

1
2
3

样例输出 #2

-1

样例 #3

样例输入 #3

2
1 9
0

样例输出 #3

0