#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);
} 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 sub3
{
ll solve(vector<int> s, vector<int> t)
{
int n = size(s);
set<ii> st;
for (int i = 0; i < n; ++i)
st.insert({t[i], s[i]});
for (int prv = 1e9; !st.empty();)
{
auto it = st.upper_bound(mp(prv, 1e9));
if (it == st.begin())
return 1;
it = prev(it);
prv = (it -> s2);
st.erase(it);
cerr << "> " << prv << '\n';
}
return 0;
}
}
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 sub2 :: 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 = 5;
// vector<int> s(n), t(n);
// for (int i = 0; i < n; ++i)
// s[i] = randint(1, 10), t[i] = randint(1, 10);
// if (!!sub1::solve(s, t) != !!sub3::solve(s, t))
// {
// cout << n << '\n';
// for (int i = 0; i < n; ++i)
// cout << s[i] << " " << t[i] << '\n';
// return 0;
// }
// }
// return 0;
// }
