#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "railroad.h"
using namespace std;
using namespace __gnu_pbds;
///#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define ff first
#define ss second
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(),(x).end()
const ll INF = 1e18;
const int nax = 16;
const int naxx =4e5 + 4;
int n;
vll s, t;
ll dp[(1 << nax)][nax];
vi adj[naxx];
vi p, rnk;
ll f(int mask, int cur)
{
//cout <<mask << ' ' << cur << '\n';
if(mask == (1 << n) - 1)
return dp[mask][cur] = 0ll;
if(dp[mask][cur] != -1)
return dp[mask][cur];
ll ans = INF;
for(int i = 0; i < n; i++)
{
if((1 << i) & mask)
continue;
ans = min(ans, f(mask + (1 << i), i) + max(0ll,t[cur] - s[i]));
}
//cout << cur << ' ' << mask << ' ' << ans << '\n';
return dp[mask][cur] = ans;
}
int findset(int x){return p[x] = p[x] == x? x: findset(p[x]);}
void unite(int i, int j)
{
int x= findset(i);
int y = findset(j);
if(x == y)
return ;
if(rnk[x] > rnk[y])
swap(x,y);
p[x]= y;
if(rnk[x] == rnk[y])
rnk[y]++;
}
ll plan_roller_coaster( vi S, vi T)
{
int N = S.size();
n = N;
for(int i = 0; i < n; i ++)
t.pb(T[i]);
for(int i = 0; i < n; i ++)
s.pb(S[i]);
if(n <= 16)
{
ll ans = INF;
memset(dp,-1,sizeof(dp));
for(int i= 0 ; i < n; i++)
{
ans = min(ans, f(( 1<< i), i));
}
return ans;
}
indexed_set nid;
nid.insert(1);
nid.insert(1e9);
for(int i = 0; i < n; i++)
{
nid.insert(s[i]);
nid.insert(t[i]);
}
int sz = nid.size();
p.assign(sz, 0);
rnk.assign(sz,0);
for(int i= 0 ; i < n;i ++)
p[i] = i;
int suf[sz + 1];
memset(suf,0,sizeof(suf));
int u =nid.order_of_key(1);
int v = nid.order_of_key(1e9);
unite(u,v);
suf[u] += 1;
suf[v] -= 1;
for(int i= 0; i < n; i++)
{
u = nid.order_of_key(s[i]);
v = nid.order_of_key(t[i]);
suf[u] += 1;
suf[v] -= 1;
unite(u,v);
}
int cur = 0;
for(int i = 0;i < sz - 1; i ++)
{
cur += suf[i];
if(cur > 0)
return 2;
if(cur == 0 )
unite(i, i + 1);
}
for(int i = 1; i < sz; i ++)
if(findset(i) != findset(0))
return 1;
return 0 ;
}
/*
int main()
{
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}
*/
