#include<bits/stdc++.h>
using namespace std;

#define int long long

#define pii pair<int,int>

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N+1),w(N+1);
	for(int i=1;i<=N;i++){
		cin>>v[i];
	}
	for(int i=1;i<=N;i++){
		cin>>w[i];
	}
	vector<vector<int>>g(N+1);
	vector<int>s;
	for(int i=N;i>=1;i--){
		while(!s.empty()&&v[s.back()]<=v[i]){
			s.pop_back();
		}
		g[s.empty()?0:s.back()].push_back(i);
		s.push_back(i);
	}
	auto solve=[&](int y)->pii{
		auto dfs=[&](auto self,int i)->pair<pii,pii>{
			pii a{},b{};
			for(int j:g[i]){
				auto [p,q]=self(self,j);
				a.first+=p.first;
				a.second+=p.second;
				if(q.first-p.first>b.first){
					b.first=q.first-p.first;
					b.second=q.second-p.second;
				}
			}
			b.first+=a.first+w[i];
			b.second+=a.second;
			if(w[i]>y){
				a.first+=w[i]-y;
				a.second++;
			}
			if(b.first-y>a.first){
				a.first=b.first-y;
				a.second=b.second+1;
			}
			return{a,b};
		};
		return dfs(dfs,0).first;
	};
	int l=0,h=1e16;
	while(l<h){
		int m=(l+h)/2;
		auto[x,c]=solve(m);
		if(c<=K){
			h=m;
		}
		else{
			l=m+1;
		}
	}
	auto[x,c]=solve(h);
	cout<<x+K*h<<'\n';
	return 0;
}