/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 枚のトーストと M 枚の皿があります。M は \frac{N}{2} 以上 N 以下の整数です。i 枚目のトーストの美味しさは A_{i} です。
この N 枚のトーストを以下の 2 つの条件を満たすように M 枚の皿にのせます。
- 1 枚の皿にのせることができるトーストは高々 2 枚
- どのトーストも必ずどれか 1 つの皿にのっている
j 枚目の皿にのっているトーストの美味しさの総和 (皿に 1 枚もトーストがのっていない場合は 0 ) を B_{j} として、 アンバランス度を \sum_{j=1}^{M} B_{j}^{2} とします。
アンバランス度としてありうる最小の値を求めてください。
制約
- 1\leq N\leq 2\times 10^{5}
- \frac{N}{2}\leq M\leq N
- 1\leq A_{i}\leq 2\times 10^{5}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N M
A_{1} A_{2} \cdots A_{N}
出力
答えを出力してください。
入力例 1
5 3 1 1 1 6 7
出力例 1
102
1,2 枚目のトーストを 1 枚目の皿に、 3,4 枚目のトーストを 2 枚目の皿に、 5 枚目のトーストを 3 枚目の皿にのせると、 (1+1)^{2}+(1+6)^{2}+7^2=102 より、アンバランス度が 102 になります。
アンバランス度が 102 未満になるのせ方は存在しないため、 102 を出力します。
1,2,3 枚目のトーストを全て同じ皿にのせることはできないことに注意してください。
入力例 2
2 1 167 924
出力例 2
1190281
入力例 3
12 9 22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740
出力例 3
61968950639
Score : 300 points
Problem Statement
We have N slices of toast and M plates. M is an integer between \frac{N}{2} and N, inclusive. The i-th slice of toast has a deliciousness of A_{i}.
Let us put the N slices of toast on the M plates to satisfy the following two conditions.
- Each plate can have at most two slices of toast on it.
- Every slice of toast is on some plate.
Let B_{j} be the sum of the deliciousness of the toast on the j-th plate (0 if the plate has no toast on it). Then, let the unbalancedness be \sum_{j=1}^{M} B_{j}^{2}.
Find the minimum possible value of the unbalancedness.
Constraints
- 1\leq N\leq 2\times 10^{5}
- \frac{N}{2}\leq M\leq N
- 1\leq A_{i}\leq 2\times 10^{5}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_{1} A_{2} \cdots A_{N}
Output
Print the answer.
Sample Input 1
5 3 1 1 1 6 7
Sample Output 1
102
If you put the first and second slices on the first plate, the third and fourth slices on the second plate, and the fifth slice on the third plate, we have (1+1)^{2}+(1+6)^{2}+7^2=102, so the unbalancedness is 102.
There is no way to put them to make the unbalancedness less than 102, so print 102.
Note that you cannot put the first, second, and third slices on the same plate.
Sample Input 2
2 1 167 924
Sample Output 2
1190281
Sample Input 3
12 9 22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740
Sample Output 3
61968950639