#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int MOD = 2004010501; //MOD > 2e9
const Int INF = 1e18;
const int MAX = 2e5 + 100;
int num_elems;
Int s[MAX], t[MAX];
Int cost[20][20];
Int dp[1 << 16][16];
void minimize(Int& var, const Int& val) { if (val < var) var = val; }
/*
view each road as a graph node, then "railroads" are, in fact, just edges between nodes.
sort increasingly by s
*/
Int subtask2() {
for (int i = 0; i < num_elems; i++)
for (int j = 0; j < num_elems; j++) cost[i][j] = max(0LL, t[i] - s[j]);
for (int msk = 0; msk < (1 << num_elems); msk++)
for (int pos = 0; pos < num_elems; pos++) dp[msk][pos] = INF;
for (int i = 0; i < num_elems; i++) dp[1 << i][i] = 0;
for (int msk = 0; msk < (1 << num_elems); msk++)
for (int pos = 0; pos < num_elems; pos++) if (dp[msk][pos] < INF)
for (int nxt = 0; nxt < num_elems; nxt++) if (((msk >> nxt) & 1) == 0)
minimize(dp[msk | (1 << nxt)][nxt], dp[msk][pos] + cost[pos][nxt]);
Int ans = INF;
const int FULL = (1 << num_elems) - 1;
for (int pos = 0; pos < num_elems; pos++)
minimize(ans, dp[FULL][pos]);
return ans;
}
pair<int,int> sections[MAX];
int pos[MAX], indices[MAX], list[MAX];
bool mark[MAX];
bool cmp(const int& i, const int& j) { return (pos[i] == pos[j]) ? i > j : pos[i] > pos[j]; }
int subtask3() {
for (int i = 1; i <= num_elems; i++) sections[i] = make_pair(s[i], t[i]);
sort(sections + 1, sections + 1 + num_elems);
for (int i = 1; i <= num_elems; i++) {
//min a, such that s[a] >= t[i]. If all all s[a] < t[i]?
pos[i] = num_elems + 1;
int lo = 1, hi = num_elems;
while (lo <= hi) {
int mid = (lo+hi) >> 1;
if (sections[mid].first < sections[i].second) lo = mid + 1;
else pos[i] = mid, hi = mid - 1;
}
indices[i] = i, ::list[i] = i;
}
sort(indices + 1, indices + 1 + num_elems, cmp);
int last = num_elems;
for (int j = 1; j <= num_elems; j++) {
const int& i = indices[j];
int sav = -1; bool found = false;
for (;last >= pos[i] and !found; --last) {
if (::list[last] == i) sav = last;
if (!mark[::list[last]]) mark[::list[last]] = found = true;
}
if (!found and j > 1) return MOD;
if (sav != -1) swap(::list[++last], ::list[sav]);
}
return 0;
}
Int solve()
{
if (num_elems <= 16) return subtask2();
return subtask3();
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
::num_elems = (int) s.size();
for (int i = 0; i < num_elems; i++) ::s[i] = s[i], ::t[i] = t[i];
return solve();
}
