#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define MP make_pair
const ll INF = 1ll << 55;
ll dijkstra(auto adj, int s, int f) {
int n = adj.size();
vector<bool> vis(n);
vector<ll> d(n, INF);
d[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push(MP(0, s));
while (!pq.empty()) {
auto [_, v] = pq.top();
pq.pop();
if (vis[v]) continue;
vis[v] = true;
for (auto [u, w] : adj[v]) if (d[v]+w < d[u]) {
d[u] = d[v]+w;
pq.push(MP(d[u], u));
}
}
return d[f];
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
int n = x.size();
int m = l.size();
vector<vector<pair<int, int>>> adj(n + 16*m);
auto add_edge = [&](int v, int u, int w) {
adj[v].eb(u, w);
adj[u].eb(v, w);
};
vector<vector<int>> add(n), del(n);
for (int i=0; i<m; i++) {
add[l[i]].pb(i);
del[r[i]].pb(i);
}
int to_add = n;
set<pair<int, int>> S;
vector<pair<int, int>> last(m, MP(-1, -1));
for (int i=0; i<n; i++) {
for (int j : add[i]) S.insert(MP(y[j], j));
int prv_y = 0, prv_v = i;
for (auto [Y, j] : S) {
if (h[i]<Y) break;
add_edge(prv_v, to_add, Y-prv_y);
{
auto [k, last_x] = last[j];
if (k != -1) add_edge(k, to_add, x[i] - last_x);
last[j] = MP(to_add, x[i]);
}
prv_y = Y;
prv_v = to_add;
to_add++;
}
for (int j : del[i]) S.erase(MP(y[j], j));
}
ll ans = dijkstra(adj, s, g);
if (ans==INF) return -1;
return ans;
}
