题目描述

给定一个长度为$n$ 的非负整数序列$a_1,a_2,...a_n$

你可以对该序列进行最多$k$次操作。

每次操作选择两个非0 的元素$a_i$和$a_j$，然后选择一个整数$c(0\le c\le a_i)$，使得$a_i$减少$c$,$a_j$增加$c$。

请问，在操作全部完成后，序列中的最大值和最小值之差是多少。

例如，如果初始序列为$[5,5,5,5]$ 而$k=1$，则一种最优方案是将$a_2$减少5，将$a_4$增加5，得到序列$[5,0,5,10]$，这样最大值和最小值之差为10。

再例如，如果序列中的所有元素都为0，则无法进行任何操作，所以最大值和最小值之差也为0。

输入描述

第一行两个整数$n,k(1 \le k< n\le 10^5)$

第二行$n$个整数:$a_1,a_2,...,a_n(0\le a_i\le 10^9)$

输出描述

一个整数，表示可以得到的最大差值。

样例1

输入

4 1
5 5 5 5

输出

10

样例2

输入

3 2
0 0 0

输出

0