Problem Description

In Takahashi Country, there are $ N $ vacant houses. These houses are numbered from $ 1 $ to $ N $ and are arranged in a straight line from west to east, each spaced $ 1 $ kilometer apart. That is, the $ i $th house is located $ i $ kilometers east from a reference point.

$ M $ families are moving into the country. The $ i $th family consists of $ P_i $ people. These $ M $ families need to be assigned one vacant house each, and no house should be assigned to more than one family.

Your goal is to maximize the "distance among residents" by assigning the houses optimally. The "distance among residents" is defined as the sum of the distances between the houses of all pairs of people who have moved in.

Find the maximum value of the "distance among residents" when the houses are assigned optimally.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ P_1 $ $ P_2 $ : $ P_M $

• The first line contains the number of vacant houses in Takahashi Country, an integer $N(2\ ≦\ N\ ≦\ 10^6)$, and the number of families moving in, an integer $M(2\ ≦\ M\ ≦\ min(N,\ 1,000))$, separated by spaces.
• The next $ M $ lines contain the number of people in the $ i $th family, $P_i(1\ ≦\ P_i\ ≦\ 100)$.

Output Format

Output the maximum value of the "distance among residents" on a single line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 3
1
1
2

Sample Output #1

11

Sample Input #2

10 10
3
1
4
1
5
9
2
6
5
3

Sample Output #2

2998

Sample Input #3

20 10
2
7
1
8
2
8
1
8
2
8

Sample Output #3

9852

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $2\ ≦\ N\ ≦\ 10$, you will be awarded $ 10 $ points.
• If you solve the dataset where $2\ ≦\ N\ ≦\ 10^6$, you will be awarded an additional $ 90 $ points, totaling $ 100 $ points.

Sample Explanation 1

Consider the first family as A, the second family as B, and the third family as C and D. Assigning the first family to the 1st house, the second family to the 2nd house, and the third family to the 4th house, the distances between each pair are as follows:
- Distance between A and B: $ 1 $
- Distance between A and C: $ 3 $
- Distance between A and D: $ 3 $
- Distance between B and C: $ 2 $
- Distance between B and D: $ 2 $
- Distance between C and D: $ 0 $
Thus, the total is $ 11 $, which is the maximum "distance among residents".

见题面 Input 部分

见题面 Output 部分