Untitled

import sys

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    k = int(data[1])
    a = [int(x) for x in data[2:]]
    
    costs = [[0] * n for _ in range(n)]
    for i in range(n):
        c_min = a[i]
        c_max = a[i]
        row = costs[i]
        for j in range(i, n):
            val = a[j]
            if val < c_min: c_min = val
            if val > c_max: c_max = val
            length = j - i + 1
            if length % 2 == 1:
                row[j] = length * c_max
            else:
                row[j] = length * c_min
                
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    
    for b in range(1, k + 1):
        next_dp = [float('inf')] * (n + 1)
        for i in range(b, n + 1):
            best = float('inf')
            for j in range(b - 1, i):
                current = dp[j] + costs[j][i - 1]
                if current < best:
                    best = current
            next_dp[i] = best
        dp = next_dp
        
    print(dp[n])

if __name__ == "__main__":
    solve()