//#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//.find_by_order(1); по индексу
//.order_of_key(1);

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve();

int32_t main() {
#ifdef LOCAL
    freopen("Input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

constexpr int MAXN = 1e3 + 3;
constexpr ll INF = 1e18;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<vector<vector<ll>>> col(n + 1, vector<vector<ll>>(k, vector<ll>(k, 0)));
    vector<vector<vector<ll>>> ver(n + 1, vector<vector<ll>>(k, vector<ll>(k, 0)));
    vector<vector<ll>> sum(n + 1, vector<ll>(k, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < k; ++j) {
            ll mx = -1, ind = -1;
            for (int l = 0; l < k; ++l) {
                if (sum[i - 1][l] - ver[i - 1][l][j] + max((col[i - 1][l][j] + 1) + a[i - 1], ver[i - 1][l][j]) > mx) {
                    mx = sum[i - 1][l] - ver[i - 1][l][j] + max((col[i - 1][l][j] + 1) + a[i - 1], ver[i - 1][l][j]);
                    ind = l;
                }
            }
            sum[i][j] = mx;
            col[i][j] = col[i - 1][ind];
            col[i][j][j]++;
            ver[i][j] = ver[i - 1][ind];
            ver[i][j][j] = max((col[i - 1][ind][j] + 1) + a[i - 1], ver[i - 1][ind][j]);
        }
    }
    ll ans = -INF;
    for (int i = 0; i < k; ++i) {
        ans = max(ans, sum[n][i]);
    }
    cout << ans << '\n';
}