엘리베이터

루스네(Rusnė)는 어느 건물의 $N$층에 살며 매일 건물에 설치된 엘리베이터를 이용한다. 어느 날 그녀는 건강을 위해 엘리베이터로는 최대 $K$개의 층 구간만큼만 이동하기로 마음먹었다. 그런데 이 건물은 층과 층 사이 구간의 높이(계단 수로 측정)가 서로 다르고, 루스네는 영리해서 자기 발로는 계단을 최대한 적게 오르고 싶어 한다.

건물의 모든 구간 높이가 주어진다. 엘리베이터로는 최대 $K$개의 구간만 이동할 수 있을 때, 루스네가 자기 발로 올라야 하는 계단 수의 최솟값을 구하여라. (루스네는 엘리베이터를 원하는 만큼 여러 번 타고 내릴 수 있다.)

첫째 줄에 두 정수 $N$과 $K$가 주어진다. $N$은 루스네가 사는 층, $K$는 엘리베이터로 이동하기로 한 구간의 최대 개수이다.

이어서 $N$개의 줄이 주어진다. $i$번째 줄에는 정수 $a_i$가 하나씩 주어지며, 이는 $i-1$층과 $i$층 사이 구간의 높이를 계단 수로 나타낸 것이다 ($i$는 $1$부터 $N$까지).

건물의 층은 $0$층부터 $N$층까지 번호가 매겨진다. $0$층은 지면 높이이며, 엘리베이터는 모든 층에서 부를 수 있다.

루스네가 집으로 올라가며 자기 발로 올라야 하는 계단 수의 최솟값을 정수 하나로 출력한다.

• $0 \le K < N \le 10000$
• $1 \le a_i \le 1000$