#include <bits/stdc++.h>
struct Way {
int l;
int r;
int y;
};
struct Tower {
int x;
int y;
};
long long solve(std::vector<Tower> towers, std::vector<Way> ways, int s, int g) {
int n = towers.size();
if (!s && g == n - 1) {
std::map<int, int> all;
std::map<int, int64_t> forward, back;
all[0] = 1;
forward[0] = 0;
back[0] = 0;
std::vector<int> add[n], remove[n];
for (auto i : ways) {
add[i.l].push_back(i.y);
if (i.r != n - 1) remove[i.r].push_back(i.y);
}
remove[0].push_back(0);
for (int i = 0; i < n; i++) {
for (auto j : add[i]) {
// std::cerr << "add " << j << std::endl;
int64_t dist = 1000000000000000000;
auto itr = forward.upper_bound(j);
if (itr != forward.begin()) dist = std::min(dist, std::prev(itr)->second + (j - std::prev(itr)->first));
itr = back.lower_bound(j);
if (itr != back.end()) dist = std::min(dist, itr->second + (itr->first - j));
all[j]++;
itr = forward.upper_bound(j);
if (itr == forward.begin() || (std::prev(itr)->second - std::prev(itr)->first) > dist - j) {
forward[j] = dist;
while (itr != forward.end() && itr->second - itr->first > dist - j) itr = forward.erase(itr);
}
itr = back.lower_bound(j);
if (itr == back.end() || itr->first + itr->second > dist + j) {
back[j] = dist;
while (itr != back.begin() && std::prev(itr)->first + std::prev(itr)->second > dist + j) back.erase(std::prev(itr));
}
}
for (auto j : remove[i]) {
// std::cerr << "remove " << j << std::endl;
if (all[j] == 1) {
if (forward.count(j)) {
auto itr = all.upper_bound(j);
if (itr != all.end()) forward[itr->first] = forward[j] + (itr->first - j);
forward.erase(j);
}
if (back.count(j)) {
auto itr = all.lower_bound(j);
if (itr != all.begin()) back[std::prev(itr)->first] = back[j] + (j - std::prev(itr)->first);
back.erase(j);
}
all.erase(j);
} else all[j]--;
}
/*
std::cerr << "all : ";
for (auto i : all) std::cerr << "{" << i.first << "," << i.second << "} ";
std::cerr << std::endl;
std::cerr << "forward : ";
for (auto i : forward) std::cerr << "{" << i.first << "," << i.second << "} ";
std::cerr << std::endl;
std::cerr << "back : ";
for (auto i : back) std::cerr << "{" << i.first << "," << i.second << "} ";
std::cerr << std::endl;*/
}
if (!back.size()) return -1;
int64_t res = back.begin()->second + back.begin()->first;
if (res > 500000000000000000) return -1;
return res + (towers.back().x - towers.front().x);
}
assert(0);
return -1;
}
long long min_distance(std::vector<int> a, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
std::vector<Tower> towers;
for (int i = 0; i < (int) a.size(); i++) towers.push_back({a[i], h[i]});
std::vector<Way> ways;
for (int i = 0; i < (int) l.size(); i++) ways.push_back({l[i], r[i], y[i]});
return solve(towers, ways, s, g);
}
/*
int ri() {
int n;
scanf("%d", &n);
return n;
}
int main() {
}
*/
