점수를 최대로

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

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

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

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

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

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