#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 16;
const ll inf = 1e18;
ll dp[(1<<maxn)+10][maxn], adj[maxn][maxn];
ll plan_roller_coaster(vector<int> s, vector<int> t){
int n = (int)s.size();
vector<pair<int,int>> tmp(n);
for (int i = 0; i < n; i++)
tmp[i] = {s[i],t[i]};
sort(tmp.begin(), tmp.end());
for (int i = 0; i < n; i++)
s[i] = tmp[i].first, t[i] = tmp[i].second;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j)
adj[i][j] = max(0,t[i]-s[j]);
memset(dp, 63, sizeof dp);
for (int mask = 1; mask < (1 << n); mask++){
for (int v = 0; v < n; v++){
if (!(mask & (1<<v)))
continue;
int sub = mask^(1<<v);
if (sub == 0 and v == 0)
dp[mask][v] = 0;
else
for (int u = 0; u < n; u++)
if (sub & (1 << u))
dp[mask][v] = min(dp[mask][v], dp[sub][u]+adj[u][v]);
}
}
ll answer = inf;
for (int i = 0; i < n; i++)
answer = min(answer, dp[(1<<n)-1][i]);
return answer;
}
