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 A₁, A₂, . . . , A_N (1 ≤ A_i ≤ 10⁶) — the sequence elements.

출력 형식

Output one number — minimal possible value of a splittings.

예제 입력 1

5 1
1 2 3 4 5

예제 출력 1

5

예제 입력 2

5 2
1 2 3 4 5

예제 출력 2

6