#include<iostream>
#include<cstdio>

const int MAX_N = 8000, MAX_G = 800;
const long long INF = 1ll<<62;
int N,G;
long long s[MAX_N+10];
struct {long long val; int opt;} dp[MAX_N+10][MAX_G+10];

inline long long cost(int l, int r) { return (s[r]-s[l-1])*1ll*(r-l+1); }

int main()
{
    scanf("%d%d\n", &N, &G);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d\n", s+i);
        s[i] += s[i-1];
    }
    if (N <= G)
    {
        printf("%lld", s[N]);
        return 0;
    }

    for (int i = 1; i <= N; ++i)
    {
        dp[i][i].val = s[i];
        dp[i][i].opt = std::max(i-1, 1);

        dp[i][1].val = i*s[i];
        dp[i][1].opt = 1;
    }

    for (int i = 2; i <= N; ++i)
        for (int j = std::min(G, i-1); j > 1 ; --j)
        {
            dp[i][j].val = INF;

            int to = j==G?i-1:dp[i][j+1].opt;
            for (int k = dp[i-1][j].opt; k <= to; ++k)
            {
                long long val = dp[k][j-1].val + cost(k+1, i);
                if (dp[i][j].val > val)
                {
                    dp[i][j].val = val;
                    dp[i][j].opt = k;
                }
            }
        }

    printf("%lld", dp[N][G].val);
}