[USACO Dec07]书架

成绩 0 开启时间 2013年01月18日 星期五 04:15
折扣 0.8 折扣时间 2013年01月18日 星期五 04:15
允许迟交 关闭时间 2013年01月18日 星期五 04:15
输入文件 shelf.in 输出文件 shelf.out

译 by CmYkRgB123

Farmer John最近为奶牛图书馆购买了一个书架,书架的下层很快装满了书,现在只剩下了顶层书架有空间。

在 N (1 ≤ N ≤ 20,000)头牛中,第i头牛的身高为 Hi (1 ≤ Hi ≤ 10,000)。书架的高度为 B (1 ≤ B ≤ 2,000,000,007),且 B 小于所有奶牛的身高之和。

书架的顶层高于最高的牛的身高,但是若干个奶牛可以站成一摞,这样总高度就是它们的身高之和。总高度应大于等于书架的高度,奶牛才能取到书。

但是越多的奶牛站成一摞,它们就越危险。你的工作就是找到一个集合,使得尽量少的奶牛站成一摞,当然,它们要能取到顶层的书。

输入

  • 第 1 行: 两个整数: N , B
  • 第 2..N+1 行: 第 i+1 行包含一个整数 Hi

输出

  • 第 1 行: 一个整数,这个使得尽量少的奶牛站成一摞取得顶层的书的集合中奶牛的个数。

样例输入

6 40
6
18
11
13
19
11

样例输出

3