算法社团为校园开放日准备了 N 种不同图案的纪念章。第 i 种图案共有 B_i 枚。现在需要使用恰好 K 个托盘分装这些纪念章，其中 K 是偶数。

分装时必须满足：

• 同一个托盘中只能放置同一种图案的纪念章；
• 同一种图案的纪念章可以分到多个托盘中；
• 可以不使用完某种图案的全部纪念章；
• 托盘允许为空。

分装结束后，学校会按照托盘中的纪念章数量从多到少排序，将数量较多的前 \frac K2 个托盘送给来访学校，算法社团保留剩余的 \frac K2 个托盘。数量相同的托盘以任意顺序排列，不会影响双方得到的纪念章总数。

请你设计分装方案，使算法社团最终保留的纪念章数量尽可能多，并输出这个最大值。

第一行输入两个整数 N,K，表示纪念章图案数量和托盘数量。

第二行输入 N 个整数 B_1,B_2,\ldots,B_N，表示每种纪念章的数量。

输出一行一个整数，表示算法社团最多能够保留多少枚纪念章。

样例说明 1

可以准备 4 个各装有 4 枚纪念章的托盘：

• 第 1 种图案装满一个托盘；
• 第 2 种图案取出 4 枚，装满一个托盘；
• 第 3 种图案取出 8 枚，分装到两个托盘。

学校送出其中两个托盘，社团保留另外两个托盘，因此可以保留 4+4=8 枚纪念章。

样例说明 2

最优方案不一定让所有非空托盘中的纪念章数量相同，某些图案剩余的纪念章也可能影响答案。

数据范围

对于所有测试数据，保证：

• 1\le N\le1000；
• 2\le K\le1000，且 K 为偶数；
• 1\le B_i\le1000。

本题共 10 个测试点，每个测试点 10 分。

特殊性质 A：K=2。

特殊性质 B：对于所有 i，均有 B_i=1。

月赛26年8月贪心枚举