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.

Input

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

Output one number - minimal possible value of a splittings.

Examples