시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 24 7 7 31.818%

문제

You are given a sequence A of N positive integers. Let’s define “value of a splitting” the sequence to K blocks as a sum of maximums in each of K blocks. For given K find the minimal possible value of splittings.

입력

First line of the input file contains two integers N and K. Next line contains N integers A1, A2, . . . , AN (1 ≤ Ai ≤ 106) — the sequence elements.

출력

Output one number — minimal possible value of a splittings.

예제 입력

5 1
1 2 3 4 5

예제 출력

5

예제 입력 2

5 2
1 2 3 4 5

예제 출력 2

6

힌트