19521번 - House Moving 다국어

There are $N$ houses numbered 1 through $N$. The distance between the house $i$ and the house $j$ is $|i - j|$.

You want to assign $M$ families to these houses. There are $P_i$ people in the $i$-th family. No two families can be assigned to the same house.

Your objective is to maximize the distance of residents. For each (unordered) pair of two people among the $M$ families, compute the distance between their houses. The distance of residents is defined as the sum of these values for all pairs.

Compute the maximum possible value of the distance of residents.

$N$ $M$
$P_1$
$P_2$
$\vdots$
$P_M$

Print the answer in a single line.

• $2 \leq N \leq 10^6$
• $2 \leq M \leq \min(N, 1000)$
• $1 \leq P_i \leq 100$

In the Sample 1, let A be the member of the first family, B be the member of the second family, and C, D be the members of the third family.

In the optimal assignment, the first family shuold go to the house $1$, the second family should go to the house $2$, and the third family shuold go to the house $4$.

• The distance between A and B: $1$
• The distance between A and C: $3$
• The distance between A and D: $3$
• The distance between B and C: $2$
• The distance between B and D: $2$
• The distance between C and D: $0$

The distance of residents is $11$.