#include <bits/stdc++.h>
#include "homecoming.h"
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<ll>a,b;
ll k, n, act;
const int MAXN=501;
ll dp[MAXN][MAXN];
ll vis[MAXN][MAXN];
ll calc(ll l, ll r)
{
if(vis[l][r]==act)
return dp[l][r];
vis[l][r] = act;
ll len = (r - l + n) % n + 1;
if(len < k)
return 0;
ll gan = 0, cost = 0, i, buc;
for(i=l, buc=0; buc < len; buc++, i=(i+1)%n)
cost += b[i];
for(i=l, buc=0; buc < len - k + 1; buc++, i=(i+1)%n)
gan += a[i];
ll ma = max(gan - cost, 0ll);
for(i=l, buc=0; buc < len - 1; buc++, i=(i+1)%n)
ma = max(ma, calc(l, i) + calc((i+1)%n, r));
dp[l][r] = ma;
return ma;
}
long long int solve(int N, int K, int *A, int *B)
{
ll ans = 0, i;
n=N;
k=K;
a.resize(N);
b.resize(N);
for(i=0; i<N; i++)
{
a[i]=A[i];
b[i]=B[i];
}
ll sum=0, gan=0;
ans=max(ans,calc(i,(i+N-1)%N));
for(i=0; i<N/2; i++)
{
act++;
gan+=a[i];
sum+=b[i];
}
ans=max(ans,gan-sum);
return ans;
}
