나쁜 녀석, 승한

승한이는 친구들에게 “나쁜 녀석” 이라고 놀림을 많이 받는다. 이에 스트레스를 받은 승한이는 자신을 놀린 친구들에게 “장문의 카톡”을 보내 놀리지 말아달라고 할 예정이다.

N명의 친구들에게 모두 카톡을 한 통씩 보내기에는 돈이 부족하기 때문에 최대 M개의 카톡밖에 보내지 못한다. 따라서 승한이는 친구들을 M개의 그룹으로 나누어 카톡을 보낸다.

각 친구들과 승한이 사이의 친밀도가 A[i]로 주어졌을 때, 승한이는 카톡을 보내는 “어색함”을 최소로 하고자 한다.

그룹 A의 “어색함”은, (그룹 A의 사람수 – 1) * (그룹 A 의 사람들의 친밀도의 합) 이다.

M개의 그룹들의 “어색함”의 총합을 최소로 하도록 승한이를 도와 N 명의 사람들을 적절히 그룹 짓자.

( 예제는 채점 데이터와 무관하다. )

입력 형식

첫 줄에 N, M 이 입력된다. ( 5 <= M <= N <= 5000 )

2번째 줄부터 N+1 번째 줄까지 각 사람의 친밀도를 나타내는 정수가 주어진다. (10000 이하)

출력 형식

최소 “어색함”을 출력한다.

입력 예제 1

5 2

1

2

3

4

5

출력 예제

21

설명 : (1, 2, 3)  (4, 5) 로 묶으면 6 * 2 + 9 * 1 = 21 이 최소다.

입력 예제 2

5 2

1

2

3

4

1000

출력 예제

30

설명 : (1, 2, 3, 4)  (5) 로 묶으면 10 * 3 = 30 이 최소다.