An Amazon delivery driver has
The weight of package
The driver must split all packages into exactly
The fatigue of a group is normally equal to the square of the total weight of packages in that group.
The driver has one discount coupon. The coupon must be used on exactly one group, and for that group, the fatigue becomes equal to only the total weight of that group instead of its square.
Your task is to find the minimum possible total fatigue.
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of packages and the number of groups.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the weights of the packages.
Print a single integer — the minimum possible total fatigue after splitting the packages into exactly KaTeX can only parse string typed expression groups and using the discount coupon on exactly one group.
Input
5 2
1 2 3 4 515Split the packages as KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. The first group has fatigue KaTeX can only parse string typed expression. Use the discount coupon on the second group, whose total weight is KaTeX can only parse string typed expression. The total fatigue is KaTeX can only parse string typed expression.
Example 2:
Input
4 4
3 1 2 519Each package must be its own group. Use the coupon on package KaTeX can only parse string typed expression. The total fatigue is KaTeX can only parse string typed expression.
Example 3:
Input
3 1
10 20 3060There is only one group, so the coupon must be used on it. The total weight is KaTeX can only parse string typed expression, so the answer is KaTeX can only parse string typed expression.