题目描述

Bessie 和她的妹妹 Elsie 正在农夫约翰的浆果园里采浆果。

农夫约翰的浆果园里有 $N$棵浆果树；树 $i$ 上有 $B_i$个浆果。

Bessie 有 $K$个篮子。

每个篮子里可以装同一棵树上采下的任意多个浆果，但是不能装来自于不同的树上的浆果，因为它们的口味可能不同。

篮子里也可以不装浆果。

Bessie 想要使得她得到的浆果数量最大。

但是，农夫约翰希望 Bessie 与她的妹妹一同分享，所以 Bessie 必须将浆果数量较多的$\frac{k}{2}$个篮子给 Elsie。

这表示 Elsie 很有可能最后比 Bessie 得到更多的浆果，这十分不公平，然而姐妹之间往往就是这样。

帮助 Bessie 求出她最多可以得到的浆果数量。

输入

输入的第一行包含空格分隔的整数 $N$ 和 $K$。

第二行包含 $N$个空格分隔的整数 $B_1,B_2,…,B_N$。

输出

输出一行，包含所求的答案。

样例输入

5 4
3 6 8 4 2

样例输出

8

提示

$1≤N≤1000,$

$1≤Bi≤1000,$

$1≤K≤1000,K$ 为偶数。

如果 Bessie 在

一个篮子里装树 $2$ 的 $6$个浆果

两个篮子里每个装树 $3$ 的 $4$ 个浆果

一个篮子里装树 $4$ 的 $4$个浆果

那么她能够得到两个各装有 $4$ 个浆果的篮子，总共 $8$ 个浆果。