#include <bits/stdc++.h>
#include "homecoming.h"
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 2000000;
ll dp[2][2], A[MAX_N+1], B[MAX_N+1], SA[MAX_N+1], SB[MAX_N+1];
ll ndp[2][2];
int N, K;
ll sumA(int x, int y){
if(x==0){
return SA[y];
}
if(x<=y){
return SA[y]-SA[x-1];
}else{
return SA[N-1]-SA[x-1]+SA[y];
}
}
ll sumB(int x, int y){
if(x==0) return SB[y];
if(x<=y){
return SB[y]-SB[x-1];
}else{
return SB[N-1]-SB[x-1]+SB[y];
}
}
long long int solve(int n, int k, int *C, int *D){
N = n; K = k;
for(int i=0; i<N; i++){
A[i] = (ll)C[i];
B[i] = (ll)D[i];
if(i!=0){
SA[i] = SA[i-1] + A[i];
SB[i] = SB[i-1] + B[i];
}else{
SA[i] = A[i]; SB[i] = B[i];
}
}
dp[0][0] = 0;
dp[0][1] = 0;
dp[1][0] = A[0] - sumB(0, K-1);
dp[1][1] = A[0] - B[K-1];
for(int i=1; i<N; i++){
for(int j=0; j<2; j++){
ndp[0][j] = max(dp[0][j], dp[1][j]);
ndp[1][j] = max(dp[1][j] + A[i] - B[(i+K-1)%N], dp[0][j] + A[i] - sumB(i, (i+K-1)%N));
dp[0][j] = ndp[0][j]; dp[1][j] = ndp[1][j];
}
}
return max(dp[0][0], dp[1][1]);
}
