#include <bits/stdc++.h>
#include "walk.h"
#define MAX 100000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
ll dist[3000];
ll isq[3000];
vector<vi> G;
void dijktra(ll u){
memset(isq,0,sizeof isq);
for(int i=0;i<=3000;i++){
dist[i]=MAX;
}
priority_queue<ii,vi,greater<ii> > pq;
dist[u]=0;
isq[u]=1;
pq.push(ii(0,u));
while(!pq.empty()){
ll x=pq.top().second;
ll di=pq.top().first;
pq.pop();
isq[x]=0;
if(di>dist[x]) continue;
for(auto &v:G[x]){
ll w=v.first;
if(dist[v.second]>dist[x]+w){
dist[v.second]=dist[x]+w;
if(isq[v.second]==0){
pq.push(ii(dist[v.second],v.second));
isq[v.second]=1;
}
}
}
}
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
ll no;
no=0;
map<ii,ll> m;
for(int i=0;i<x.size();i++){
no++;
m[ii(x[i],0)]=no;
//printf("(%d,%d) %lld\n",x[i],0,no);
}
//cout<<endl;
G.resize(3010);
for(int i=0;i<y.size();i++){
ll ant=-1,id;
for(int j=l[i];j<=r[i];j++){
if(h[j]>=y[i]){
if(m[ii(x[j],y[i])]==0){
no++;
m[ii(x[j],y[i])]=no;
//printf("(%d,%d) %lld\n",x[j],y[i],no);
}
if(ant==-1){
ant=m[ii(x[j],y[i])];
id=j;
}
else{
ll dis=abs(x[j]-x[id]);
ll u=m[ii(x[j],y[i])];
G[ant].push_back(ii(dis,u));
G[u].push_back(ii(dis,ant));
ant=u;
id=j;
}
}
}
}
for(int i=0;i<x.size();i++){
ll ant=0;
for(int j=1;j<=h[i];j++){
if(m[ii(x[i],j)]!=0){
ll u=m[ii(x[i],j)];
ll v=m[ii(x[i],ant)];
ll w=abs(ant-j);
G[u].push_back(ii(w,v));
G[v].push_back(ii(w,u));
ant=j;
}
}
}
dijktra(m[ii(x[s],0)]);
// if(dist[m[ii(x[g],0)]]==MAX) dist[m[ii(x[g],0)]]=-1;
ll res=dist[m[ii(x[g],0)]];
return res;
}
