#include <bits/stdc++.h>
#define int long long
#define inf 1e18
#define ff first
#define ss second
#define all(v) v.begin() , v.end()
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

int n, k;
vector <vector <int> > dp;
vector <int> a, suf_sum, suf_val;

/// debug ///
//int dp[305][305], a[305], pref[305];
/// debug ///

void init(){
    n = min(n, k);
    a.resize(k); suf_sum.resize(k); suf_val.resize(k);
    dp.resize(n); for (auto &u: dp) u.resize(k, inf);
    for (int i = 0; i < k; i++)
        cin >> a[i];
    for (int i = k - 1; i >= 0; i--){
        suf_sum[i] = a[i];
        if (i != k - 1) suf_sum[i] += suf_sum[i + 1];
    }
    for (int i = k - 1; i >= 0; i--){
        suf_val[i] = suf_sum[i];
        if (i != k - 1) suf_val[i] += suf_val[i + 1];
    }
    for (int i = 0; i < k; i++){
        dp[0][i] = (i + 1) * a[i];
        if (i) dp[0][i] += dp[0][i - 1];
    }
}

int func(int l, int r){
    if (r == k - 1) return suf_val[l];
    return suf_val[l] - suf_val[r + 1] - suf_sum[r + 1] * (r - l + 1);
}

void solve(int L, int R, int l, int r, int h){
    if (L > R) return;
    int mid = (L + R) / 2;
    pair <ll, int> opt = {inf, -1};
    for (int i = min(mid - 1, r); i >= l; i--){
        opt = min(opt, make_pair(dp[h - 1][i] + func(i + 1, mid), i));
    }
    dp[h][mid] = opt.first;
    solve(L, mid - 1, l, opt.second, h);
    solve(mid + 1, R, opt.second, r, h);
}

int32_t main()
{
    #ifdef VBH
        freopen("input.txt" , "r" , stdin);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    init();
    for (int h = 1; h < n; h++)
        solve(h, k - 1, h - 1, k - 1, h);
    cout << dp[n - 1][k - 1];
    return 0;
}