题目描述

学校准备举办一场社团展示会，现有 $n$ 个候选活动，第 $i$ 个活动的时长为 $a_i$ 分钟。

每个活动最多安排一次，活动之间没有额外的准备时间。老师希望选出若干个活动，使它们的总时长恰好为 $T$ 分钟。在满足这个要求的前提下，安排的活动数量越少越好。

请你求出最少需要安排多少个活动。如果无法恰好凑齐 $T$ 分钟，输出 $-1$。

时长相同的两个活动仍是不同的活动，可以分别选择。当 $T=0$ 时，可以不安排任何活动，答案为 $0$。

输入格式

第一行输入两个整数 $n,T$，分别表示候选活动的数量和要求的总时长。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各个活动的时长。

输出格式

输出一个整数，表示最少需要安排的活动数量；如果无法满足要求，输出 $-1$。

3 6
4 3 3

2

1 6
3

-1

4 0
2 4 6 8

0

样例解释

样例 1 中，选择第 $2$ 个和第 $3$ 个活动，总时长为 $3+3=6$ 分钟，需要 $2$ 个活动。没有时长为 $6$ 分钟的单个活动，因此答案为 $2$。

样例 2 中，唯一的活动只能安排一次，不能将它重复安排两次，因此无法恰好凑齐 $6$ 分钟。

样例 3 中，不选择任何活动即可满足总时长为 $0$ 的要求。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le100$，$0\le T\le2000$，$1\le a_i\le2000$。所有输入均为整数。

• 子任务 1（30 分）：保证 $n\le12$ 且 $T\le30$。
• 子任务 2（30 分）：保证 $n\le50$ 且 $T\le500$。
• 子任务 3（40 分）：没有特殊限制。