给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$n$$$ 是奇数。您可以用它进行以下操作:
- 选择数组的一个元素(例如 $$$a_i$$$)并将其增加 $$$1$$$(即将其替换为 $$$a_i + 1$$$)。
您希望使用最多 $$$k$$$ 操作使数组的中位数尽可能大。
奇数数组的中位数是数组按非降序排序后的中间元素。例如,数组 $$$[1, 5, 2, 3, 5]$$$ 的中位数是 $$$3$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$($$$1 \le n \le 2 \cdot 10^5$$$,$$$n$$$ 为奇数,$$$1 \le k \le 10^9$$$)— 数组中元素的数量以及可以进行的最大操作数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
输出
打印单个整数 - 运算后可能的最大中位数。
示例
输入 #1
3 2 1 3 5
输出 #1
5
输入 #2
5 5 1 2 1 1 1
输出 #2
3
输入 #3
7 7 4 1 2 4 3 4 4
输出 #3
5
注意
在第一个示例中,您可以将第二个元素增加两次。数组将是 $$$[1, 5, 5]$$$,它的中位数是 $$$5$$$。
在第二个示例中,最佳方案是增加第二个数字,然后增加第三个和第五个数字。这样答案就是$$$3$$$。
在第三个示例中,您可以进行四种操作:增加第一、第四、第六、第七元素。这样,数组将为 $$$[5, 1, 2, 5, 3, 5, 5]$$$,中位数将为 $$$5$$$。