200256 - 先进的U盘存储

神犇改进了操作系统向U盘存储文件的方式,现在它可以把一个大文件存储到若干个U盘中——当U盘写满之后,它会提示更换下一个U盘。现在有一个大小为m MB的文件,和n个可存储容量为a_i的U盘,求至少需要用多少个U盘能把文件存完。

输入

第一行,有单个空格分隔的两个整数n,m,分别表示U盘个数和要存储的文件大小。

接下来n行,每行一个整数a_i,表示一个U盘的可存储容量。

对于100%的数据:

1\le n \le 100

1\le a_i \le 1000

1\le m \le 10^5

输出

一行,一个整数表示所需U盘的最少个数;如果无解输出-1。

样例

输入

3 5
2
1
3

输出

2

输入

3 6
2
3
2

输出

3

输入

3 7
1
2
3

输出

-1
时间限制 20 毫秒
内存限制 128 MB
统计
上一题 下一题