#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#include"homecoming.h"
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int n, k;
vector<ll> a, b;
ll naive1(int fil) {
deque<ll> dp;
const ll inf = 1ll<<50;
for(int i = 0; i <= k; i++)
dp.push_back(i == fil ? 0 : -inf);
ll best = 0, lazyadd = 0;
for(int i = 0; i < n; i++) {
ll bk = dp.back();
ll ne0 = best+lazyadd;
dp.pop_back();
dp.back() = max(dp.back(), bk);
dp.back() += a[i];
lazyadd += b[i];
best = max(best, dp.back());
if(i < n-fil) {
dp.push_front(ne0-lazyadd);
best = max(best, dp.front());
} else dp.push_front(-inf-lazyadd);
}
return best+lazyadd;
}
long long solve(int N, int K, int *A, int *B) {
n = N, k = K;
a = vector<ll>(A, A+n);
b = vector<ll>(B, B+n);
reverse(all(a));
reverse(all(b));
for(auto &i : b) i *= -1;
ll ans = 0;
for(int i = 0; i < k; i++) ans = max(ans, naive1(i));
return ans;
}
