#include<homecoming.h>
#include<bits/stdc++.h>
using namespace std;
long long int calculate (int i, int j, long long int prefiks[]){
if(i == 0){
return prefiks[j];
}else{
return prefiks[j] - prefiks[i-1];
}
}
long long solve(int N, int K, int *A, int *B){
int n = N;
int k = K;
long long int a[n];
long long int b[n];
long long int dp[n];
long long int dp1[n];
long long int sum1 = 0;
long long int pref1[2*n+1];
long long int pref2[2*n+1];
for(int i = 0; i < n; i++){
a[i] = A[i];
b[i] = B[i];
sum1 = sum1 + a[i] - b[i];
dp[i] = 0;
dp1[i] = -1e18;
}
pref1[0] = a[0];
pref2[0] = b[0];
for(int i = 1; i <= 2*n; i++){
pref1[i] = pref1[i-1] + a[i % n];
pref2[i] = pref2[i-1] + b[i % n];
}
long long int ans = 0;
ans = max (ans, sum1);
// ako ne uzimamo prvi element
for(int i = 0; i < n; i++){
if (i == 0){
long long int sum = calculate(i, i + k-1, pref2);
dp1[i] = a[i] - sum;
// dp[i] = max(dp[i], dp1[i]);
dp[i] = 0;
dp1[i] = -1e18;
}else{
dp[i] = dp[i-1];
long long int sum = calculate(i, i + k - 1, pref2);
sum = a[i] - sum;
if (i >= k){
dp1[i] = sum + dp[i-k];
}else{
dp1[i] = sum;
}
dp1[i] = max(dp1[i], dp1[i-1] + a[i] - b[(i + k - 1) % n] );
dp[i] = max(dp[i], dp1[i]);
}
}
ans = max(ans, dp[n-1]);
// ako uzimamo prvi element
int vis[n];
for (int i = 0; i < n; i++){
dp[i] = -1e18;
dp1[i] = -1e18;
vis[i] = 0;
}
for (int i = 0; i < n; i++){
if (i == 0){
long long int sum = 0;
sum = calculate(i, i + k-1, pref2);
dp1[i] = a[i] - sum;
dp[i] = dp1[i];
}else{
if (i >= k){
dp[i] = dp[i-1];
long long int sum = 0;
sum = calculate(i, i + k-1, pref2);
sum = a[i] - sum;
dp1[i] = sum + dp[i-k];
long long int ro = a[i];
ro = ro - b[(i + k - 1) % n];
dp1[i] = max(dp1[i], dp1[i-1] + ro);
dp[i] = max(dp[i], dp1[i]);
sum = 0;
sum = calculate (i, n - 1, pref1) - calculate(i, n - 1, pref2);
ans = max(ans, sum + dp[i-k]);
}else{
dp[i] = dp[i-1];
long long int ro = a[i];
if(vis[(i + k - 1) % n] == 0){
ro = ro - b[(i + k - 1) % n];
}
dp1[i] = dp1[i-1] + ro;
dp[i] = max(dp[i], dp1[i]);
}
}
}
ans = max(ans, dp[n-1]);
return ans;
}
