#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=5010;
int n;
ll dp[2*N][2*N],a[2*N],b[2*N];
/*int Dist(int l,int r){
if(l<=r) return r-l+1;
return r+n-l+1;
}*/
long long solve(int n1, int K, int *A, int *B){
n=n1;
for(int i=0;i<n;i++) a[i]=A[i],b[i]=B[i];
for(int i=n;i<2*n;i++) a[i]=a[i-n],b[i]=b[i-n];
ll res=0;
for(int l=0;l<2*n;l++){
for(int r=l;r<2*n;r++){
for(int i=l;i<=r;i++){
if(i+K-1>r) break;
ll sum=0,sum1=0;
for(int j=l;j<=i;j++) sum+=a[j];
for(int j=l;j<=i+K-1;j++) sum1+=b[j];
for(int j=i+K;j<=r;j++){
dp[l][r]=max(dp[l][r],dp[j][r]+sum-sum1);
}
}
/*for(int j=l;j!=r;j=(j+1)%n){
sum+=a[j];sum1+=b[j];
for(int i=(j+K)%n;i!=r;i++){
dp[l][r]=max(dp[l][r],dp[i][r]+sum-sum1);
}
}*/
//res=max(res,dp[l][r]);
}
}
for(int i=0;i<n;i++) res=max(res,dp[i][i+n-1]);
/*for(int r=0;r<n;r++){
for(int l=0;l<n;l++){
if(Dist(l,r)<K) continue;
ll sum=0,sum1=0;
for(int j=l,ct=K-1;ct--;j=(j+1)%n) sum1+=B[j];
for(int j=l;j!=r;j=(j+1)%n){
sum+=A[j];sum1+=B[j];
for(int i=(j+K)%n;i!=r;i++){
dp[l][r]=max(dp[l][r],dp[i][r]+sum-sum1);
}
}
res=max(res,dp[l][r]);
}
}*/
return res;
}
