29726번 - 숏코딩의 왕 브실이

문제

숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다.

브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열의 길이가 $L$일 때, 행복도를 계산하는 방법은 다음과 같다.

$$\sum_{i=1}^{L-1} (A_{i+1} - A_{i})$$

브실이는 행복도를 늘리고자 자신의 코드 길이 수열에서 최대 $M$개까지 제출 기록을 없앨 수 있다.

최대 $M$개의 제출 기록을 없앴을 때 브실이가 얻을 수 있는 행복도의 최댓값을 구해보자. 단, 행복도는 음수가 될 수 있다.

입력

첫 번째 줄에 정수 $N,ドル $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 200\ 000$; 0ドル \le M \le N-2)$

두 번째 줄에 수열 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le A_i \le 100\ 000)$

출력

최대 $M$개의 제출 기록을 없앴을 때 브실이가 얻을 수 있는 행복도의 최댓값을 출력한다.

제한

힌트