#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;
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 Tree {
vector<int> g[nmax];
void add_edge(int a, int b) {
g[a].emplace_back(b);
}
struct mdeq : Deq<ll> {
ll lazy = 0;
};
mdeq dp[nmax];
vector<bool> merge[nmax];
int calculated[nmax];
Tree(int n) {
memset(calculated, 0, sizeof(calculated));
}
template<class CB, class CB2> void calcdp(CB&& cost, CB2&& atr, int node) {
if(calculated[node]) return;
calculated[node] = 1;
vector<ll> updates;
for(auto x : g[node]) {
calcdp(cost, atr, x);
bool swapped = 0;
}
sort(all(g[node]), [&](int a, int b) { return sz(dp[a]) > sz(dp[b]); });
for(auto x : g[node]) {
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]);
}
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';
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 toleft(n), 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();
toleft.calcdp([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](int x) { return v[x]; }, 0);
toright.calcdp([&](int x) { return x == 0? 0 : -spart[x]; }, [&](int x) { return v[x]; }, 0);
ll best_cost = -1e18;
for(int P = 1; P <= n; P++) {
auto& X = toleft.dp[P];
auto& Y = toright.dp[P];
bool swapped = 0;
if(sz(X) > sz(Y)) swapped = 1, swap(X, Y);
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]);
}
if(swapped) swap(X, Y);
}
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
--
*/
