你有一颗公平的 $n$ 面骰子，各面的点数为正整数 $a_1,a_2,\ldots,a_n$。你想设计另一颗公平的 $m$ 面骰子，各面的点数为正整数 $b_1,b_2,\ldots,b_m$。每颗骰子的每一面被掷出的概率都相同。两颗骰子各自的点数都可以重复。

独立地将每颗骰子各掷一次。当且仅当新骰子的点数严格大于原骰子的点数时，新骰子获胜；平局不算获胜。

求新骰子各面点数之和 $b_1+b_2+\cdots+b_m$ 的最小可能值，使其获胜概率严格大于 $50\%$。

输入格式

第一行包含两个整数 $n,m$（$2\le n\le 50$，$1\le m\le 10^9$），分别表示原骰子和新骰子的面数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^9$），表示原骰子各面的点数。

输出格式

输出一个整数：使新骰子的获胜概率严格大于 $50\%$ 时，其各面点数之和的最小可能值。

样例

输入格式 1

6 6
1 2 3 4 5 6

输出格式 1

25

输入格式 2

3 2
1 1 2

输出格式 2

4

输入格式 3

4 4
3 7 10 11

输出格式 3

29

说明

在第一个样例中，一颗最优的新骰子各面的点数为 $1,1,2,7,7,7$，其和为 $25$。在 $36$ 种等可能的面组合中，它赢得其中的 $0+0+1+6+6+6=19$ 种。

在第二个样例中，一颗最优的新骰子各面的点数为 $2,2$。它的每一面都能击败原骰子上点数为 $1$ 的两个面，因此新骰子在 $6$ 种等可能的组合中赢得 $4$ 种。其各面点数之和为 $4$。

在第三个样例中，一颗最优的新骰子各面的点数为 $1,4,12,12$。它在 $16$ 种等可能的组合中赢得 $0+1+4+4=9$ 种，其各面点数之和为 $29$。