A. 能量水晶 / crystal
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

小 R 有 $$$n$$$ 颗能量水晶，其中第 $$$i$$$ $$$(1 \le i \le n)$$$ 颗的能量值为整数 $$$a_i$$$。

小 R 想用其中若干颗能量水晶合成一颗大水晶，用于合成的水晶必须具有相同的能量值。小 R 希望参与合成的水晶尽可能多。他可以进行至多 $$$m$$$ 次操作。每次操作可以任选一颗水晶，将其能量值增加 $$$1$$$；同一颗水晶可以被重复选择。

你需要帮助小 R 求出，进行至多 $$$m$$$ 次操作后，他最多能用多少颗能量水晶合成一颗大水晶。

Input

从标准输入读入数据。

输入的第一行包含一个正整数 $$$n$$$ 和一个非负整数 $$$m$$$，分别表示能量水晶的数量和最多可以进行的操作次数。

输入的第二行包含 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$，依次表示每颗能量水晶的能量值。

Output

输出到标准输出。

输出一行一个正整数，表示进行至多 $$$m$$$ 次操作后，小 R 最多能用多少颗能量水晶合成一颗大水晶。

Examples
Input
5 5
1 2 4 8 9
Output
3
Input
5 8
-3 -1 2 2 7
Output
4
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17831。

样例 1 解释

小 R 有 $$$5$$$ 颗能量水晶，能量值分别为 $$$1,2,4,8,9$$$。他可以对能量值为 $$$1$$$ 和 $$$2$$$ 的水晶分别操作 $$$3$$$ 次和 $$$2$$$ 次，使原来能量值为 $$$1,2,4$$$ 的三颗水晶的能量值都变成 $$$4$$$，共进行 $$$5$$$ 次操作。因此小 R 可以用 $$$3$$$ 颗能量水晶合成一颗大水晶。

样例 3

见题目目录下的 crystal/3.in 与 crystal/3.ans。

该样例满足测试点 $$$8,9$$$ 的约束条件。

样例 4

见题目目录下的 crystal/4.in 与 crystal/4.ans。

该样例满足测试点 $$$10 \sim 12$$$ 的约束条件。

数据范围

对于所有测试数据，均有：

  • $$$1 \le n \le 5 \times 10^5$$$，$$$0 \le m \le 10^{18}$$$；
  • 对于所有 $$$i$$$ $$$(1 \le i \le n)$$$，均有 $$$|a_i| \le 10^{12}$$$。
测试点编号$$$n \le$$$$$$m \le$$$$$$\max_{i=1}^{n} \lvert a_i \rvert \le$$$特殊性质
$$$1,2$$$$$$5$$$$$$10$$$$$$20$$$无
$$$3 \sim 5$$$$$$16$$$$$$1000$$$$$$20$$$无
$$$6,7$$$$$$5000$$$$$$10^6$$$$$$100$$$无
$$$8,9$$$$$$5000$$$$$$10^9$$$$$$10^5$$$无
$$$10 \sim 12$$$$$$5 \times 10^5$$$$$$10^8$$$$$$100$$$无
$$$13 \sim 15$$$$$$5 \times 10^5$$$$$$10^{18}$$$$$$10^{12}$$$A
$$$16 \sim 18$$$$$$5 \times 10^5$$$$$$10^{18}$$$$$$10^{12}$$$B
$$$19,20$$$$$$5 \times 10^5$$$$$$10^{18}$$$$$$10^{12}$$$无

特殊性质 A：对于所有 $$$i$$$ $$$(1 \le i \le n)$$$，均有 $$$a_i=i$$$。

特殊性质 B：$$$a_1,a_2,\ldots,a_n$$$ 构成等差数列。

本题满分 100 分。官方测试点共 20 个，每个测试点 5 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。