시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB64211934.545%

문제

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.

서브태스크

번호 배점 제한
1 14

1 ≤ N ≤ 100, 1 ≤ K ≤ min(N, 5)

2 18

1 ≤ N ≤ 20, 1 ≤ K ≤ min(N, 20)

3 21

1 ≤ N ≤ 100, 1 ≤ K ≤ min(N, 100)

4 47

1 ≤ N ≤ 100000, 1 ≤ K ≤ min(N, 100)

예제 입력 1

5 1
1 2 3 4 5

예제 출력 1

5

예제 입력 2

5 2
1 2 3 4 5

예제 출력 2

6

출처

Olympiad > International Zhautykov Olympiad > IZhO 2014 E번

  • 빠진 조건을 찾은 사람: yclock

채점 및 기타 정보

  • 예제는 채점하지 않는다.