#include "homecoming.h"
#include <algorithm>
using namespace std;
const int MAXN = 2000000;
const long long INFINIT = 1000000000000000000LL;
int n, k, cost[2 * MAXN], profit[MAXN];
long long cost_secv[MAXN], dp[MAXN][2], answer; // am luat sau nu 0
void calcseq() {
long long sum = 0;
for(int i = 0; i < k; i++) {
sum += cost[i];
}
cost_secv[0] = sum;
for(int i = 1; i < n; i++) {
sum += cost[i + k - 1] - cost[i - 1];
cost_secv[i] = sum;
}
}
long long solve(int N, int K, int *A, int *B) {
n = N;
k = K;
for(int i = 0; i < n; i++) {
profit[i] = A[i];
cost[i] = B[i];
}
long long answer = 0;
for(int i = 0; i < k - 1; i++) {
cost[n + i] = cost[i];
}
calcseq();
dp[0][0] = -INFINIT;
long long maxpref = 0;
for(int i = 1; i < n; i++) {
if(i >= k) {
maxpref = max(maxpref, dp[i - k][0]);
}
dp[i][0] = max(maxpref + profit[i] - cost_secv[i], dp[i - 1][0] + profit[i] - cost[i + k - 1]);
answer = max(answer, dp[i][0]);
}
for(int i = 0; i < k - 1; i++) {
cost[n + i] = 0;
}
calcseq();
dp[0][1] = profit[0] - cost_secv[0];
answer = max(answer, dp[0][1]);
maxpref = -INFINIT;
for(int i = 1; i < n; i++) {
if(i >= k) {
maxpref = max(maxpref, dp[i - k][1]);
}
dp[i][1] = max(maxpref + profit[i] - cost_secv[i], dp[i - 1][1] + profit[i] - cost[i + k - 1]);
answer = max(answer, dp[i][1]);
}
return answer;
}
