#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[10005];
// f[i][j][lock]: quãng đường dài nhất tại phút i,
// với thể lực j, và trạng thái 'lock' (0: có thể chạy, 1: đang nghỉ/must full)
int f[10005][505][2];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    // Khởi tạo
    memset(f, -1, sizeof(f));
    f[0][m][0] = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= m; j++) {
            for(int lock = 0; lock < 2; lock++) {
                if (f[i][j][lock] == -1) continue;
                int current_val = f[i][j][lock];

                // 1. Chọn NGHỈ
                // Luôn được phép nghỉ
                int next_energy = min(m, j + 1);
                int next_lock = lock;
                // Nếu nghỉ mà full năng lượng hoặc đang full rồi thì hết khóa
                if (next_energy == m) next_lock = 0;

                f[i+1][next_energy][next_lock] = max(f[i+1][next_energy][next_lock], current_val);

                // 2. Chọn CHẠY
                // Chỉ được chạy nếu energy > 0 và KHÔNG bị khóa (lock == 0)
                if (j > 0 && lock == 0) {
                    int next_e_run = j - 1;
                    // Lock vẫn giữ là 0 (vẫn có thể chạy tiếp)
                    f[i+1][next_e_run][0] = max(f[i+1][next_e_run][0], current_val + a[i+1]);
                }
            }
        }
    }

    // Kết quả là giá trị tốt nhất tại phút N, thể lực M, lock = 0
    cout << f[n][m][0] << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

#define MAXN 10005
#define MAXM 505
#define NEG_INF -1000000000

int N, M;
int D[MAXN];
int dp[2][MAXM][2]; // dp[time%2][energy][lock]

static inline int max(int a, int b) { return a > b ? a : b; }

int main() {
    if (scanf("%d %d", &N, &M) != 2) return 0;
    for (int i = 1; i <= N; i++) scanf("%d", &D[i]);

    // Khởi tạo
    for (int e = 0; e <= M; e++) dp[0][e][0] = dp[0][e][1] = NEG_INF;
    dp[0][M][0] = 0;

    for (int t = 0; t < N; t++) {
        int cur = t & 1, nxt = cur ^ 1;
        for (int e = 0; e <= M; e++) dp[nxt][e][0] = dp[nxt][e][1] = NEG_INF;

        for (int e = 0; e <= M; e++) {
            for (int lock = 0; lock <= 1; lock++) {
                int val = dp[cur][e][lock];
                if (val == NEG_INF) continue;

                // 1. Nghỉ
                int e1 = e + 1; if (e1 > M) e1 = M;
                int lock1 = (e1 == M) ? 0 : 1; // Nếu full năng lượng thì hết khóa
                // Nếu đang lock=1, nghỉ vẫn là lock=1 (trừ khi full M)
                // Nếu đang lock=0, nghỉ vẫn lock=0 (trừ khi full M)
                // Thực chất lock1 chỉ phụ thuộc năng lượng mới
                dp[nxt][e1][lock1] = max(dp[nxt][e1][lock1], val);

                // 2. Chạy
                if (e > 0 && lock == 0) {
                    int e2 = e - 1;
                    // lock vẫn là 0
                    dp[nxt][e2][0] = max(dp[nxt][e2][0], val + D[t+1]);
                }
            }
        }
    }

    printf("%d\n", dp[N&1][M][0]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n + 1, 0);
  vector<int> pre(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
  }
  // dp[i]: quãng đường dài nhất kết thúc ở phút i và thể lực đầy (M)
  vector<int> dp(n + 1, 0);

  for (int i = 0; i <= n; i++) {
    // Option 1: Tạm nghỉ ở đây (không chạy thêm)
    dp[min(n, i + 1)] = max(dp[min(n, i + 1)], dp[i]);

    // Option 2: Chạy một đoạn, rồi nghỉ
    // Chạy j phút (tốn j thể lực), nghỉ j phút (lấy lại j thể lực)
    // Tổng thời gian: 2*j. Tổng thể lực giữ nguyên.
    // Điều kiện: i + 2*j <= n, j <= m
    int maxj = min(m, (n - i) / 2);
    for (int j = 1; j <= maxj; j++) {
      // Chạy từ i+1 đến i+j
      // Thời gian kết thúc: i + 2*j
      // Thể lực về M
      dp[i + 2 * j] = max(dp[i + 2 * j], dp[i] + pre[i + j] - pre[i]);
    }
  }
  cout << dp[n] << endl;
  return 0;
}