時間制限:1000ミリ秒
メモリ制限:65536KB
問題
農夫ジョンは最近牛の図書館に本棚を買いました。しかし本棚はとても速く一杯になっていきます。今はもう空いているのは一番上の棚のみです。N頭の牛はそれぞれ身長がHi (1 ≤ Hi ≤ 10,000)でN頭の牛の身長の合計はSです。本棚の高さはB(1 ≤ B ≤ S < 2,000,000,007)です。
最も背の高い牛より高い本棚に届くためには、1匹以上の牛が他の牛の上に乗ることができます。そうしてできた高さは各牛の身長の合計になります。この高さは本棚の高さ以上でなければなりません。必要以上に牛が積み重なるのは危険です。あなたの仕事はその重ねで本棚に届くようなもののうちで最も牛の数が少ない積み重ねとなる牛の集合を見つけることです。
入力
1行目: スペースで区切られた2つの整数NとB
2~N+1行目: i+1行目は整数1つ: Hi
出力
1行: 本棚に届くような積み重ねで最も牛の数が小さくてすむときの頭数
入力の例
6 40 6 18 11 13 19 11
出力の例
3
出典
USACO 2007 December Bronze