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 ≤ 105, 1 ≤ k ≤ min(n, 100)). Next line contains n integers A1, A2, ..., An (1 ≤ Ai ≤ 106) - the sequence elements.

Output

Output one number - minimal possible value of a splittings.