该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现在有 $N$ 片吐司和 $M$ 个盘子，其中 $M$ 满足：

$\left\lceil \frac{N}{2} \right\rceil$ 是$N/2$ 向上取整

第 $i$ 片吐司的美味值为 $A_i$。

你需要将这 $N$ 片吐司放到这 $M$ 个盘子中，并满足以下条件：

• 每个盘子上最多放 2 片吐司；
• 每一片吐司都必须放在某一个盘子上。

设第 $j$ 个盘子上吐司美味值之和为 $B_j$。如果该盘子为空，则 $B_j=0$。

定义这次摆放方案的 不均衡度 为：

解释：

请你求出最小可能的不均衡度。

输入格式

第一行包含两个整数：

第二行包含 $N$ 个整数：

输出格式

输出一个整数，表示最小可能的不均衡度。

输入输出样例

输入 #1

5 3
1 1 1 6 7

输出 #1

102

说明 #1

例如，可以采用如下放法：

• 第 1、2 片吐司放在第 1 个盘子；
• 第 3、4 片吐司放在第 2 个盘子；
• 第 5 片吐司放在第 3 个盘子。

则不均衡度为：

可以证明，不存在比 $102$ 更小的方案，因此输出 $102$。

注意，不能把第 1、2、3 片吐司同时放在同一个盘子里，因为每个盘子最多只能放 2 片吐司。

输入 #2

2 1
167 924

输出 #2

1190281

输入 #3

12 9
22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740

输出 #3

61968950639

数据范围

• $1 \le N \le 2 \times 10^5$
• $\left\lceil \dfrac{N}{2} \right\rceil \le M \le N$
• $1 \le A_i \le 2 \times 10^5$
• 所有输入均为整数