#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
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);
for (int i = 1; i <= n; i++)
{
dp[i][i-1] = 0;
for (int j = i; j <= n; j++)
{
dp[i][j] = dp[i][j-1];
if (j - k + 1 < i)
continue;
long long sum = 0;
for (int p = j - k + 2; p <= j; p++)
sum -= b[p-1];
for (int p = j - k + 1; p >= i; p--)
{
sum -= b[p-1];
sum += a[p-1];
dp[i][j] = max(dp[i][j], sum + dp[i][p-1]);
}
}
}
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;
}
*/
