#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()
using ll = long long;
using ii = pair<int, int>;
const ll inf = 1e18 + 69;
namespace sub1
{
ll solve(vector<int> s,vector<int> t)
{
int n = size(s);
vector<ii> v(n);
for (int i = 0; i < n; ++i)
v[i] = {s[i], t[i]};
sort(v.begin(), v.end());
ll mn = inf;
do
{
ll ctr = 0;
for (int i = 0, cur = 1; i < n; ++i)
{
ctr += max(0, cur - v[i].f1);
cur = v[i].s2;
}
mn = min(mn, ctr);
if (ctr == 8)
{
for (auto [l, r] : v)
cout << l << " " << r << " -- ";
cout << '\n';
for (auto [l, r] : v) if (l < r)
cout << l << " " << r << " __ ";
cout << '\n';
for (auto [l, r] : v) if (l >= r)
cout << l << " " << r << " -- ";
cout << "\n\n";
}
} while (next_permutation(v.begin(), v.end()));
return mn;
}
}
namespace sub2
{
ll solve(vector<int> s, vector<int> t)
{
int N = size(s);
vector<vector<ll>> dp(N, vector<ll>(1 << N, inf));
const auto rc = [&](const auto &self, int id, int mask) -> ll
{
if (mask == (1 << N) - 1)
return 0;
if (dp[id][mask] != inf)
return dp[id][mask];
for (int i = 0; i < N; ++i) if (~mask >> i & 1)
dp[id][mask] = min(dp[id][mask], max(0, t[id] - s[i]) + self(self, i, mask | (1 << i)));
return dp[id][mask];
};
ll res = inf;
for (int i = 0; i < N; ++i)
res = min(res, rc(rc, i, 1 << i));
return res;
}
}
namespace full
{
ll solve(vector<int> s, vector<int> t)
{
vector<int> zip = { 1 };
for (int x : s)
zip.pb(x);
for (int x : t)
zip.pb(x);
sort(zip.begin(), zip.end());
zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
for (int &x : s)
x = (int)(lower_bound(zip.begin(), zip.end(), x) - zip.begin());
for (int &x : t)
x = (int)(lower_bound(zip.begin(), zip.end(), x) - zip.begin());
int n = size(s);
vector<ii> v1, v2;
for (int i = 0; i < n; ++i)
{
if (s[i] < t[i]) v1.pb({s[i], t[i]});
else v2.pb({s[i], t[i]});
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end(), [](ii &x, ii &y){
return x.s2 < y.s2;
});
vector<ll> pfx(size(zip), 0);
int mn = 1e9;
for (int i = 0, j = 0; i+1 < size(v1); ++i)
{
if (v1[i].s2 > v1[i+1].f1)
{
pfx[v1[i+1].f1]++;
pfx[v1[i].s2]--;
mn = min(mn, v1[i+1].f1);
}
}
for (auto [l, r] : v2)
{
if (l < mn)
{
pfx[l]++, pfx[mn]--;
mn = l;
}
pfx[r]--, pfx[l]++;
}
for (int i = 1; i < size(pfx); ++i)
pfx[i] += pfx[i-1];
ll res = 0;
for (int i = 0; i+1 < size(pfx); ++i)
res += 1ll * max(0ll, pfx[i]) * (zip[i+1] - zip[i]);
return res;
}
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
// cerr << "sub1 " << sub1 :: solve(s, t) << '\n';
// cerr << "sub3 " << sub3 :: solve(s, t) << '\n';
return full :: solve(s, t);
}
// int main() {
// mt19937 RNG(69);
// const auto randint = [&](int l, int r) -> int
// {
// return uniform_int_distribution<int>(l, r)(RNG);
// };
// for (int rep = 0; rep < 100; ++rep)
// {
// cerr << "rep " << rep << '\n';
// int n = 7;
// vector<int> s(n), t(n);
// for (int i = 0; i < n; ++i)
// s[i] = randint(1, 10), t[i] = randint(1, 10);
// if (sub2 :: solve(s, t))
// {
// cout << n << '\n';
// for (int i = 0; i < n; ++i)
// cout << s[i] << " " << t[i] << '\n';
// return 0;
// }
// }
// return 0;
// }
