#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 25e4 + 5;
int K;
namespace Persistente {
template<typename T>
struct PVector {
struct Vector {
T val;
Vector *L, *R;
} *nil = new Vector{0, 0, 0}, *root = nil;
PVector() {
nil -> L = nil -> R = nil;
root = nil;
}
using ns = Vector*;
T access(int p, ns node, int cl = 0, int cr = nmax) const {
int mid = (cl + cr) >> 1;
if(p == mid) { return node -> val; }
if(p < mid) { return access(p, node -> L, cl, mid - 1); }
return access(p, node -> R, mid + 1, cr);
}
pair<T*, ns> overwrite(int p, ns node, int cl = 0, int cr = nmax) {
int mid = (cl + cr) >> 1;
if(p == mid) { auto tK = new Vector{node -> val, node -> L, node -> R}; return make_pair(&(tK -> val), tK); }
if(p < mid) { auto a = overwrite(p, node -> L, cl, mid - 1); return make_pair(a.first, new Vector{node -> val, a.second, node -> R}); }
auto a = overwrite(p, node -> R, mid + 1, cr);
return make_pair(a.first, new Vector{node -> val, node -> L, a.second});
}
T operator[](const int& a) const {
return access(a, root);
}
T* operator()(const int& a) {
auto [x, y] = overwrite(a, root);
root = y;
return x;
}
};
template<typename T>
struct Deq {
int dim = 0, ldim = 0;
PVector<T> v;
void push_front(T x) { auto H = v(dim); (*H) = x; dim++;}
T operator[](const int& x) { return v[dim - x - 1]; }
T& operator()(const int& x) { auto H = v(dim - x - 1); return (*H); }
void resize(int k) {
ldim = max(ldim, dim - k);
}
int size() { return dim - ldim; }
};
struct mdeq : Deq<ll> {
ll lazy = 0;
};
};
namespace Nepersistente {
template<typename T>
struct Deq {
vector<T> v;
int ldim = 0;
void push_front(T x) { v.emplace_back(x); }
T& operator()(const int& x) { return rbegin(v)[x]; }
T operator[](const int& x) const { return rbegin(v)[x]; }
void resize(int k) {
ldim = max(sz(v) - k, ldim);
return;
}
int size() { return sz(v) - ldim; }
}; // trebuie facut persistent
struct mdeq : Deq<ll> {
ll lazy = 0;
};
}
template<typename Cine>
struct Tree {
vector<int> g[nmax];
void add_edge(int a, int b) {
g[a].emplace_back(b);
}
Cine dp[nmax];
vector<bool> merge[nmax];
int calculated[nmax];
Tree(int n) {
memset(calculated, 0, sizeof(calculated));
}
template<int persistent, class CB, class CB2, class CB3> void calcdp(CB&& cost, CB2&& atr, CB3&& after_convolution, int node) {
if(calculated[node]) return;
calculated[node] = 1;
vector<ll> updates;
for(auto x : g[node]) {
calcdp<persistent>(cost, atr, after_convolution, x);
bool swapped = 0;
}
sort(all(g[node]), [&](int a, int b) { return sz(dp[a]) > sz(dp[b]); });
for(auto x : g[node]) {
if(persistent) {
auto T = dp[x];
T.resize(K + 1);
if(sz(T) > sz(dp[node]))
swap(T, dp[node]);
updates.resize(max(sz(updates), sz(T)), (ll)(-1e18));
for(int i = 0; i < sz(T); i++)
updates[i] = max(T[i] + T.lazy - dp[node].lazy, updates[i]);
}
else {
auto& T = dp[x];
T.resize(K + 1);
if(sz(T) > sz(dp[node]))
swap(T, dp[node]);
for(int i = 0; i < sz(T); i++)
dp[node](i) = max(T[i] + T.lazy - dp[node].lazy, dp[node](i));
}
}
for(int i = 0; i < sz(updates); i++)
dp[node](i) = max(dp[node](i), updates[i]);
dp[node].push_front(cost(node) - dp[node].lazy);
dp[node].lazy += atr(node);
//cerr << node << ": ";
//for(int i = 0; i < sz(dp[node]); i++)
//cerr << dp[node][i] + dp[node].lazy << ' ';
//cerr << '\n';
after_convolution(node);
return;
}
template<class CB> void propmerge(CB&& atr, vector<int> order) {
return;
}
};
ll spart[nmax];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n >> K;
for(int i = 1, x; i <= n; i++) {
cin >> spart[i];
spart[i] += spart[i - 1];
}
vector<int> v(n + 1);
for(int i = 1; i <= n; i++) cin >> v[i];
//for(int i = 1; i <= n; i++) {
//if(v[i] >= 10000)cerr << i << ' ';
//}cerr << '\n';
Tree<Persistente::mdeq> toleft(n);
Tree<Nepersistente::mdeq> toright(n);
vector<int> st;
for(int i = 1; i <= n; i++) {
while(sz(st) && v[st.back()] <= v[i]) { toright.add_edge(st.back(), i); toleft.add_edge(i, st.back()); st.pop_back(); }
toleft.add_edge(0, i);
if(sz(st)) toright.add_edge(st.back(), i), toleft.add_edge(i, st.back());
st.emplace_back(i);
}
st.clear();
for(int i = n; i > 0; i--) {
while(sz(st) && v[st.back()] <= v[i]) { toleft.add_edge(st.back(), i); toright.add_edge(i, st.back()); st.pop_back(); }
toright.add_edge(0, i);
if(sz(st)) toleft.add_edge(st.back(), i), toright.add_edge(i, st.back());
st.emplace_back(i);
}
st.clear();
ll best_cost = -1e18;
toleft.calcdp<1>([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](int x) { return v[x]; }, [&](int a) {;}, 0);
toright.calcdp<0>([&](int x) { return x == 0? 0 : -spart[x]; }, [&](int x) { return v[x]; }, [&](int P) {
if(P == 0) return;
auto& X = toleft.dp[P];
auto& Y = toright.dp[P];
if(sz(X) > sz(Y)) {
for(int j = 0; j < min(K, sz(Y)); j++) {
int i = K - j - 1;
if(i >= sz(X)) continue;
best_cost = max(best_cost, X[i] + Y[j] + X.lazy + Y.lazy - v[P]);
}
}
else {
for(int i = 0; i < min(K, sz(X)); i++) {
int j = K - i - 1;
if(j >= sz(Y)) continue;
best_cost = max(best_cost, X[i] + Y[j] + X.lazy + Y.lazy - v[P]);
}
}
},
0);
cout << best_cost << '\n';
}
/**
Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/
