一张纸包含一个由 n 个整数 a1, a2, ..., an 组成的数组。你的任务是找到这个数组中出现次数最多的数字。
但是,在查找这样的数字之前,您最多可以执行 k 个以下操作 - 从数组中选择任意元素并将其加 1。换句话说,允许将某个数组元素增加 1 最多不超过 k 次(允许多次增加数组的同一元素)。
你的任务是在执行不超过 k 个允许的操作后找到数组中某个数字的最大出现次数。如果有多个这样的数字,您的任务就是找到最小的一个。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 105; 0 ≤ k ≤ 109) — 数组中的元素数量和允许执行的操作数量。
第三行包含 n 个整数 a1, a2, ..., an (|ai| ≤ 109) 的序列 — 初始数组。行中的数字由单个空格分隔。
输出
在一行中打印两个数字——执行最多 k 个允许的操作后数组中某个数字出现的最大次数,以及达到给定最大值的最小数字。用空格分隔打印的数字。
示例
输入 #1
5 3 6 3 4 0 2
输出 #1
3 4
输入 #2
3 4 5 5 5
输出 #2
3 5
输入 #3
5 3 3 1 2 2 1
输出 #3
4 2
注意
在第一个示例中,您的任务是将数组的第二个元素增加一次,并将数组的第五个元素增加两次。因此,我们得到序列 6,4,4,0,4,其中数字 4 出现了 3 次。
在第二个示例中,您不需要执行单个操作或将每个元素加一。如果我们什么都不做,我们会得到数组 5, 5, 5,如果我们分别加一,我们会得到 6, 6, 6。在这两种情况下,最大出现次数都等于 3。所以我们什么也不做,因为数字 5 小于数字 6。
在第三个示例中,我们应该将第二个数组元素增加一次,将第五个元素增加一次。因此,我们得到序列 3,2,2,2,2,其中数字 2 出现了 4 次。