29767번 - 점수를 최대로

단대소프트고에는 교실 $N$개가 있다. 교실은 $1$번부터 $N$번까지 $1, 2, \ldots, N$ 순서로 연달아 있다.

학교 밖에는 $K$명의 학생들이 있다. $K$명의 학생은 학교에 들어가기 전 학생마다 목적지 교실을 정하게 된다. $j$번째 학생의 목적지는 $B_j$번 교실이다. 학생들의 목적지는 모두 달라야 한다. $j$번째 학생은 $1$번 교실, $2$번 교실, $\ldots, B_j$번 교실까지 모든 교실에 들어갔다 나오게 된다. 마지막 교실까지 들어갔다 나오게 되면 아무 교실도 방문하지 않고 다시 학교 밖으로 나간다.

모든 학생의 방문이 끝나면, 교실의 점수를 구할 수 있다. $i$번째 교실의 점수는 $A_i$ × ($i$번째 교실에 학생이 들어갔다 나온 횟수)가 된다. 학생들은 학교에 들어가기 전 방문 후의 교실의 점수의 합이 최대가 되도록 의논하여 목적지를 정한다. 이때 방문이 끝난 후 모든 교실의 점수의 합을 구해보자.

첫째 줄에 $N$과 $K$가 공백으로 구분되어 입력된다. $(1≤K≤N≤300\,000)$

둘째 줄에 정수 $A_1, A_2, ... A_N$이 공백으로 구분되어 입력된다. $(-10^8≤A_i≤10^8)$

첫째 줄에 방문이 끝난 후 모든 교실의 점수의 합을 출력한다.