#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
const long long inf = 1e18;
long long solve(int n, int k, int *a, int *b)
{
vector <vector <long long> > dp(n+1);
for (int i = 1; i <= n; i++)
dp[i].resize(n+1);
vector <long long> pra(n+1, 0), prb(n+1, 0);
for (int i = 1; i <= n; i++)
{
pra[i] = pra[i-1] + a[i-1];
prb[i] = prb[i-1] + b[i-1];
}
for (int i = 1; i <= n; i++)
{
dp[i][i-1] = 0;
long long curr_max = -inf;
for (int j = i; j <= n; j++)
{
dp[i][j] = dp[i][j-1];
if (j - k + 1 < i)
continue;
int pos = j - k + 1;
curr_max = max(curr_max, prb[pos-1] - pra[pos-1] + dp[i][pos-1]);
dp[i][j] = max(dp[i][j], curr_max - prb[j] + pra[pos]);
}
}
long long bb = 0;
for (int i = 1; i <= n; i++)
{
bb -= b[i-1];
bb += a[i-1];
}
long long ans = max(bb, dp[1][n]);
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
{
long long curr = dp[i][j];
for (int p = j + 1; p <= n; p++)
{
curr -= b[p-1];
int nxt = p + k - 1;
if (nxt > n)
nxt -= n;
if (nxt >= p || nxt < i)
curr += a[p-1];
}
for (int p = 1; p < i; p++)
{
curr -= b[p-1];
if (p + k - 1 < i)
curr += a[p-1];
}
ans = max(ans, curr);
}
return ans;
}
/*
const int maxn = 1e3 + 3;
int n, k;
int a[maxn], b[maxn];
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
cout << solve(n, k, a, b) << endl;
}
*/
