#include "railroad.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e18 + 5;
void upd(ll& a, ll b) { a = min(a, b); }
long long bruteforce(vector<int> s, vector<int> t)
{
int n = s.size();
// slow
vector<vector<ll> > dp((1 << n), vector<ll>(n, inf));
for (int m = 0; m < (1 << n); m++)
{
if (!m)
{
for (int j = 0; j < n; j++) dp[(1 << j)][j] = 0;
continue;
}
for (int i = 0; i < n; i++) if (m & (1 << i))
{
for (int j = 0; j < n; j++) if (!(m & (1 << j)))
{
ll di = max(0, t[i] - s[j]);
upd(dp[m | (1 << j)][j], dp[m][i] + di);
}
}
}
return *min_element(dp.back().begin(), dp.back().end());
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
if (a.first != b.first) return a.first < b.first;
return a.second > b.second;
}
vector<ll> b(60); // baza
bool add(ll x)
{
for (ll i = b.size() - 1; i >= 0; i--) if (x & (1ll << i))
{
if (b[i]) x ^= b[i];
else return b[i] = x, true;
}
return false;
}
long long zero(vector<int> s, vector<int> t) // >= 0 budu vystupy, < 0 budu vstupy
{
b.assign(60, 0);
int n = s.size();
vector<pair<int, int> > v;
v.push_back({ 1, 0 });
for (int i = 0; i < n; i++) v.push_back({ s[i], -i - 1 }), v.push_back({ t[i], i + 1 });
sort(v.begin(), v.end(), cmp);
vector<ll> val(n + 1, 0);
for (int i = 0; i <= n; i++) val[i] = uniform_int_distribution<ll>(0, (1ll << 60ll) - 1ll)(rng);
ll pf = 0;
int in = 0, ou = 0;
for (pair<int, int> p : v)
{
if (p.second >= 0) ou++;
else in++;
if (ou < in) return 1;
pf ^= val[abs(p.second)];
if (ou == in)
{
if (!add(pf)) return 1;
pf = 0;
}
}
return 0;
}
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
if (s.size() <= 16) return bruteforce(s, t);
return zero(s, t);
}
