#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#include "railroad.h"
long long f(std::vector<int> const &s, std::vector<int> const &t) {
std::set<std::pair<int, int>> w;
for (size_t i{}; i < s.size(); ++i) w.emplace(s[i], t[i]);
std::vector<std::pair<int, int>> v;
v.push_back(*w.begin());
w.erase(w.begin());
while (!w.empty()) {
auto it = w.lower_bound({v.back().second, v.back().first});
if (it == w.end()) --it;
v.push_back(*it);
w.erase(it);
}
// for (auto [a, b] : v) std::cerr << a << ' ' << b << '\n';
long long R{};
for (size_t i{}; i + 1 < v.size(); ++i) R += std::max(0, v[i].second - v[i + 1].first);
// std::cerr << R << '\n';
return R;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
auto a = f(s, t);
for (size_t i{}; i < s.size(); ++i) {
std::swap(s[i], t[i]);
s[i] *= -1;
t[i] *= -1;
}
auto b = f(s, t);
return std::min(a, b);
}
