#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include"wiring.h"
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 100010
struct qry{
ll ida,idb,cost;
bool operator<(const qry&key)const{
if(this->ida!=key.ida)return this->ida>key.ida;
if(this->idb!=key.idb)return this->idb>key.idb;
return this->cost>key.cost;
};
};
qry qrys(ll p,ll q,ll r){
qry gen;
gen.ida=p;
gen.idb=q;
gen.cost=r;
return gen;
}
priority_queue<qry> Q;
unordered_map<ll,ll> dist[N];
unordered_set<ll> ava[N];
void ad(ll x,ll y){
ava[x].insert(y);
}
bool av(ll x,ll y){
return ava[x].find(y)!=ava[x].end();
}
ll lastsc[2*N];
ll lastchi[2*N],lastchj[2*N];
ll ruia[N],ruib[N];
ll min_total_length(vector<int> a,vector<int> b){
ruia[0]=0; for(int i=0;i<a.size();i++)ruia[i+1]=ruia[i]+a[i];
ruib[0]=0; for(int i=0;i<b.size();i++)ruib[i+1]=ruib[i]+b[i];
for(int i=0;i<2*N;i++){
lastsc[i]=1e17;
lastchi[i]=0;
lastchj[i]=0;
}
Q.push(qrys(0,0,0));
ad(a.size()-1,b.size()-1);
ll q=0;
for(int p=0;p<a.size();p++){
for(;q<b.size()&&a[p]>b[q];q++){}
if(q-1>=0)ad(p,q-1);
if(q<b.size())ad(p,q);
//cout<<"$"<<p<<" "<<q<<endl;
}
q=0;
for(int p=0;p<b.size();p++){
for(;q<a.size()&&b[p]>a[q];q++){}
if(q-1>=0)ad(q-1,p);
if(q<a.size())ad(q,p);
//cout<<"$"<<p<<" "<<q<<endl;
}
/*
for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){
if(av(i,j))cout<<"#"<<i<<" "<<j<<endl;
}*/
while(!Q.empty()){
ll i=Q.top().ida;
ll j=Q.top().idb;
ll cost=Q.top().cost+abs(a[i]-b[j]);
Q.pop();
if(av(i,j)==0)continue;
if(dist[i].find(j)!=dist[i].end()){
if(dist[i][j]<=cost)continue;
}
ll base=i-j+N;
ll ch=lastsc[base]+abs(ruia[i+1]-ruia[lastchi[base]+1]-(ruib[j+1]-ruib[lastchj[base]+1]));
chmin(cost,ch);
lastsc[base]=cost;
lastchi[base]=i,lastchj[base]=j;
if(i+1<a.size()){
Q.push(qrys(i+1,j,cost));
}
if(j+1<b.size()){
Q.push(qrys(i,j+1,cost));
}
//cout<<"dist:"<<i<<" "<<j<<" "<<cost<<endl;
dist[i][j]=cost;
}
return dist[a.size()-1][b.size()-1];
}/*
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
vector<ll> a,b;
ll n,m; cin>>n>>m;
for(int i=0;i<n;i++){
ll x; cin>>x;
a.push_back(x);
}
for(int i=0;i<m;i++){
ll x; cin>>x;
b.push_back(x);
}
cout<<min_total_length(a,b)<<endl;
}*/
