#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
ll N, M, K, S, T, dis[1000];
vector<pll> E[1000], ver[1000], hor[1000];
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
N = x.size(), M = l.size();
for (int i = 0; i < N; i++)
{
++K;
ver[i].emplace_back(pll(0, K));
if(i == s)
S = K;
if(i == g)
T = K;
}
for (int i = 0; i < M; i++)
for (int j = l[i]; j <= r[i]; j++)
if (y[i] <= h[j])
{
++K;
ver[j].emplace_back(pll(y[i], K));
hor[i].emplace_back(pll(x[j], K));
}
for (int i = 0; i < N; i++)
{
sort(ver[i].begin(), ver[i].end());
for (int j = 0; j + 1 < ver[i].size(); j++)
E[ver[i][j].S].emplace_back(ver[i][j + 1].S, ver[i][j + 1].F - ver[i][j].F),
E[ver[i][j + 1].S].emplace_back(ver[i][j].S, ver[i][j + 1].F - ver[i][j].F);
}
for (int i = 0; i < M; i++)
{
sort(hor[i].begin(), hor[i].end());
for (int j = 0; j + 1 < hor[i].size(); j++)
E[hor[i][j].S].emplace_back(hor[i][j + 1].S, hor[i][j + 1].F - hor[i][j].F),
E[hor[i][j + 1].S].emplace_back(hor[i][j].S, hor[i][j + 1].F - hor[i][j].F);
}
for (int i = 0; i <= K; i++)
dis[i] = 1e18;
priority_queue<pll, vector<pll>, greater<pll>> pq;
dis[S] = 0;
pq.push(pll(0, S));
while(!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if(d > dis[u])
continue;
for (auto [v, w] : E[u])
if(dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
pq.push(pll(dis[v], v));
}
}
return (dis[T] >= 1e18 ? -1 : dis[T]);
}
