#include "homecoming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000000000000
#define umax(x,y) x=max(x,(y))
#define pw(x) (1<<(x))
ll psum[2000002],psum2[2000002];
ll dp[2][2000002];
long long solve(int N, int K, int *A, int *B) {
ll res=0;
for(int i=1;i<=N;i++) {psum[i]=psum[i-1]+B[i-1];psum2[i]=psum2[i-1]+A[i-1];}
for(int j=0;j<=K;j++) {
for(int i=1;i<=N+1;i++) for(int t=0;t<2;t++) dp[t][i]=-inf;
dp[1][j+1]=(j-K+1>=1?A[j-K+1-1]:0)-psum[j];
for(int i=j+1;i<=N;i++) {
if(dp[1][i]!=-inf) {
if(i<N) umax(dp[1][i+1],dp[1][i]-B[i-1]+(i-K+1>=1?A[i-K+1-1]:0));
else {
int amount=max(0,min(j+1,K));
umax(dp[1][N+1],dp[1][i]-B[i-1]+psum2[i-K+amount]-psum2[i-K]);
}
umax(dp[0][i+1],dp[1][i]);
}
if(dp[0][i]!=-inf) {
if(i+K<=N) {
umax(dp[1][i+K],dp[0][i]+A[i-1]-(psum[i+K-1]-psum[i-1]));
}
else {
int amount=max(0,min(N+1-i,j+N+1-i-K+1));
umax(dp[1][N+1],dp[0][i]+psum2[i+amount-1]-psum2[i-1]-(psum[N]-psum[i-1]));
}
umax(dp[0][i+1],dp[0][i]);
}
}
umax(res,max(dp[0][N+1],dp[1][N+1]));
}
umax(res,psum2[N]-psum[N]);
return res;
}
