#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define popcnt __builtin_popcount
pii a[200100];
ll dp[100100][17];
bool cmp(int a, int b){
return popcnt(a) < popcnt(b);
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = s.size();
vector<int> q;
for(int i=1; i<(1 << n); i++){
q.pb(i);
for(int j=0; j<n; j++) dp[i][j] = 1e18;
}
sort(q.begin(), q.end(), cmp);
for(int i=0; i<n; i++){
dp[(1 << i)][i] = 0;
}
for(int k: q){
vector<int> l, r;
for(int i=0; i<n; i++){
if((k & (1 << i))) l.pb(i);
else r.pb(i);
}
for(int x: l){
for(int y: r){
dp[k + (1 << y)][y] = min(dp[k + (1 << y)][y], dp[k][x] + max(t[x] - s[y], 0));
}
}
}
ll ans = 1e18;
for(int i=0; i<n; i++){
ans = min(ans, dp[(1 << n) - 1][i]);
}
return ans;
}
