House Moving

시간 제한1초메모리 제한256 MB

요약

크기가 주어진 M개의 가족을 N개의 집에 서로 다르게 배치해 모든 사람 쌍의 거리 합을 최대로 만든다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

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$ .

예제3

예제 1
입력
```
4 3
1
1
2
```
예상 출력
```
11
```
예제 2
입력
```
10 10
3
1
4
1
5
9
2
6
5
3
```
예상 출력
```
2998
```
예제 3
입력
```
20 10
2
7
1
8
2
8
1
8
2
8
```
예상 출력
```
9852
```