import java.math.*;
import java.util.*;
class walk {
class Pair implements Comparator <Pair> {
int first, second;
Pair () {}
Pair (int first, int second) {
this.first = first; this.second = second;
}
public int compare(Pair a, Pair b) {
if(a.first == b.first) return a.second - b.second;
return a.first - b.first;
}
}
class Node implements Comparator <Node> {
int dist, pos, line;
Node () {}
Node (int dist, int pos, int line) {
this.dist = dist; this.pos = pos; this.line = line;
}
public int compare(Node a, Node b) {
if(a.dist != b.dist) return a.dist - b.dist;
if(a.pos != b.pos) return a.pos - b.pos;
return a.line - b.line;
}
}
public long min_distance(int[] x, int[] h, int[] l, int[] r, int[] y, int f, int g) {
int n = x.length;
int m = y.length;
TreeSet <Pair> [] s = new TreeSet [n];
for(int i = 0; i < n; i++) {
s[i] = new TreeSet <> (new Pair());
}
for(int i = 0; i < m; i++) {
for(int j = l[i]; j <= r[i]; j++) {
if(y[i] <= h[j]) {
s[j].add(new Pair(y[i], i));
}
}
}
s[f].add(new Pair(0, m));
s[g].add(new Pair(0, m + 1));
TreeMap <Pair, Integer> dist = new TreeMap <> (new Pair());
TreeSet <Node> q = new TreeSet <> (new Node());
q.add(new Node(0, f, m));
dist.put(new Pair(f, m), 0);
while(!q.isEmpty()) {
int pos = q.first().pos;
int line = q.first().line;
int current = q.first().dist;
q.remove(new Node(current, pos, line));
int high = (line >= m) ? 0 : y[line];
if(dist.get(new Pair(pos, line)) != current) continue;
// System.out.println(pos + " " + line + " " + current);
ArrayList <Pair> can = new ArrayList <> ();
if(line < m) {
for(int j = pos + 1; j <= r[line]; j++) {
if(h[j] >= high) {
can.add(new Pair(j, line));
break;
}
}
for(int j = pos - 1; j >= l[line]; j--) {
if(h[j] >= high) {
can.add(new Pair(j, line));
break;
}
}
}
Pair a = s[pos].lower(new Pair(high, line));
Pair b = s[pos].higher(new Pair(high, line));
if(a != null) {
can.add(new Pair(pos, a.second));
}
if(b != null) {
can.add(new Pair(pos, b.second));
}
for(Pair i : can) {
int nxtH = (i.second >= m) ? 0 : y[i.second];
int d = current + Math.abs(x[pos] - x[i.first]) +
Math.abs(high - nxtH);
// System.out.println(i.first + " and " + i.second + " = " + d);
if(dist.get(i) == null || dist.get(i) > d) {
dist.put(new Pair(i.first, i.second), d);
q.add(new Node(d, i.first, i.second));
}
}
}
return dist.get(new Pair(g, m + 1)) == null ? -1 : dist.get(new Pair(g, m + 1));
}
}
