#include "railroad.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 17;
ll dp[maxn][(1<<maxn)], n;
bool comparator(pii a, pii b) {
return a.second <= b.first && b.second > a.first;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = (int) s.size();
if(n <= 16) {
for(int i=1;i<(1<<n);i++) {
//cout<<i<<": \n";
for(int c=0;c<n;c++) {
if(!((1<<c)&i)) continue;
dp[c][i] = LLONG_MAX;
if(__builtin_popcount(i) == 1) {
dp[c][i] = 0;
}
else {
for(int p=0;p<n;p++) {
if(!((1<<p)&i) || c == p) continue;
ll cost = max(0LL, 1LL * t[p] - s[c]);
dp[c][i] = min(dp[c][i], dp[p][(i^(1<<c))] + cost);
}
}
//cout<<c<<" - "<<dp[c][i]<<"\n";
}
}
ll result = LLONG_MAX;
for(int i=0;i<n;i++) {
result = min(result, dp[i][(1<<n)-1]);
}
return result;
}
else {
vector<pair<int,int> > v;
for(int i=0;i<n;i++) {
v.pb(mp(s[i], t[i]));
}
sort(v.begin(), v.end(), comparator);
return 0;
}
}
