#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
const long long INF = 1e16;
const int MAX_N = 4e6 + 1;
deque<int> maxVal;long long sumB[MAX_N], dp[MAX_N], val[MAX_N];
void add( int i ) { while ( !maxVal.empty() && val[i] > val[maxVal.back()] ) maxVal.pop_back(); maxVal.push_back( i );}
void rem( int i ) { if ( !maxVal.empty() && maxVal.front() == i ) maxVal.pop_front();}
long long getVal( int i ) { if ( maxVal.front() == 0 ) return dp[0]; return dp[maxVal.front()] - (sumB[i + 1] - sumB[maxVal.front()]);}
long long solve( int n, int k, int a[], int b[] ) { long long ans = 0; for ( int i = n; i <= n + k; i++ ) sumB[i] = 0; for ( int i = n - 1; i >= 0; i-- ) sumB[i] = sumB[i + 1] + b[i]; for ( int take = 0; take <= 1; take++ ) { if ( !take ) { long long s = 0; for ( int i = 0; i <= k; i++ ) { dp[n + i] = -s; s += b[i]; } } else { for ( int i = 0; i <= k; i++ ) dp[n + i] = 0; } maxVal.clear(); for ( int i = n + k - 1; i >= n; i-- ) { val[i] = dp[i] + sumB[i - 1]; add( i ); } long long maxA = dp[n + k]; for ( int i = n - 1; i >= 0; i-- ) { dp[i] = -INF; if ( i >= k * take ) { dp[i] = max( getVal( i ), maxA ); val[i] = dp[i] + sumB[i]; add( i ); } rem( i + k ); maxA = max( maxA, dp[i + k] - (sumB[i + 1] - sumB[i + k]) ); maxA = maxA - b[i] + a[i]; } ans = max( ans, getVal( -1 ) ); ans = max( ans, maxA ); } return ans;}
