11858번 - K blocks 서브태스크다국어

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.