include

include

include

include

using namespace std; int main() {

int N, K;
cin >> N >> K;
vector<int> a(N + 1);
for (int i = 1; i <= N; ++i) {
    cin >> a[i];
}
vector<long long> sum(N + 1, 0);
for (int i = 1; i <= N; ++i) {
    sum[i] = sum[i - 1] + a[i];
}
vector<vector<int>> max_range(N + 1, vector<int>(N + 1, 0));
for (int l = 1; l <= N; ++l) {
    max_range[l][l] = a[l];
    for (int r = l + 1; r <= N; ++r) {
        max_range[l][r] = max(max_range[l][r - 1], a[r]);
    }
}
vector<vector<long long>> dp(N + 1, vector<long long>(K + 2, LLONG_MAX));
dp[0][0] = 0;
for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= K + 1; ++j) {
        for (int k = 0; k < i; ++k) {
            if (dp[k][j - 1] != LLONG_MAX) {
                long long waste = (long long)max_range[k + 1][i] * (i - k) - (sum[i] - sum[k]);
                if (dp[i][j] > dp[k][j - 1] + waste) {
                    dp[i][j] = dp[k][j - 1] + waste;
                }
            }
        }
    }
}
cout << dp[N][K + 1] << endl;
return 0;

}