← 返回题目列表

Codeforces · 609/A

A. USB 闪存驱动器

中文机器翻译题面 查看原题

Sean 正在尝试将大文件保存到 USB 闪存驱动器。他有 n 个 USB 闪存驱动器,容量分别为 a1、a2、...、1 兆字节。文件大小等于 m 兆字节。

查找写入 Sean 的文件所需的最小 USB 闪存驱动器数量(如果他可以在驱动器之间拆分文件)。

输入

第一行包含正整数 n (1 ≤ n ≤ 100) — USB 闪存驱动器的数量。

第二行包含正整数 m (1 ≤ m ≤ 105) — Sean 文件的大小。

接下来的 n 行中的每一行都包含正整数 ai (1 ≤ ai ≤ 1000) — USB 闪存驱动器的大小(以兆字节为单位)。

保证答案存在,即。 e.所有ai的总和不小于m。

输出

打印写入 Sean 文件的 USB 闪存驱动器的最小数量(如果他可以在驱动器之间拆分文件)。

示例

输入 #1

3
5
2
1
3

输出 #1

2

输入 #2

3
6
2
3
2

输出 #2

3

输入 #3

2
5
5
10

输出 #3

1

注意

在第一个示例中,Sean 仅需要两个 USB 闪存驱动器 - 第一个和第三个。

在第二个示例中,Sean 需要全部三个 USB 闪存驱动器。

在第三个示例中,Sean 只需要一个 USB 闪存驱动器,他可以使用任何可用的 USB 闪存驱动器 - 第一个或第二个。