Problem Description

Takahashi decided to distribute \( N \) chicks into \( M \) cages. The chicks are numbered from 1 to \( N \), and the size of chick \( i \) is \( A_i \).

Due to the small size of the cages, each chick experiences stress equal to the sum of the sizes of all chicks in the same cage (including itself).

Find the minimum total stress experienced by the chicks.

Input Format

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

\( N \) \( M \) \( A_1 \) \( A_2 \) \( ... \) \( A_{N} \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

5 3
3 6 2 15 9

Sample Output #1

55

Sample Input #2

13 4
4 3 9 1 3 8 2 6 11 9 2 15 40

Sample Output #2

304

Sample Input #3

4 2
1000000000 1000000000 1000000000 1000000000

Sample Output #3

8000000000

Notes/Hints

Constraints

• \( 1 \leq M \leq N \leq 2{,}000 \)
• \( 1 \leq A_i \leq 10^9 \)
• All given inputs are integers

Sample Explanation 1

• When the chicks are placed in cages as \( (1,2),(3,5),(4) \), the stress experienced is \( 9+9+11+15+11 = 55 \), which is the minimum.

Sample Explanation 3

• Note that the answer can be very large.

见题面 Input 部分

见题面 Output 部分