← 返回题目列表

AtCoder · cpsco2019_s3_b

B. 气球

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

配点 : 200 点

問題文

在竞争性专业练习活动中,气球会分发给在比赛期间解决问题的参与者。这次的管理团队中,有一位能够预知未来的通灵者,总共 原来你需要 M 气球。

現在、N 彩色气球就在手边,彩色 i (=1, 2, \ldots, N) 气球 有 a_i 件。在这个总数中 选择 M 气球。我想尽量减少所选气球中出现的颜色数量。编写一个程序来查找颜色类型的最少数量。

制約

  • 1 \le N \le 10^5
  • 1 \le M \le 10^9
  • 1 \le a_i \le 10^9
  • a_1 + a_2 + \dots + a_N \ge M
  • 提供的所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。

N M
a_1 a_2 \ldots a_N

出力

请将您的答案打印在一行上。


入力例 1

5 17
4 5 7 9 2

出力例 1

3

例如,颜色 1 气球 如果您使用 4 個、色 3 气球 如果您使用 6 個、色 4 气球 如果您使用 7 如果你使用碎片 3 按类型 您可以准备 17 气球。


入力例 2

2 9
3 6

出力例 2

2

您几乎可以使用任何气球。


入力例 3

10 9
1 2 3 4 5 6 7 8 9 10

出力例 3

1

入力例 4

10 129
12 42 13 25 32 19 14 9 21 12

出力例 4

5