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 contains two integers n and k (1 ≤ n ≤ 10^5
, 1 ≤ k ≤ min(n, 100)). Next line contains n integers A[1]
, A[2]
, ..., A[n]
(1 ≤ A[i]
≤ 10^6
) - the sequence elements.
Output one number - minimal possible value of a splittings.