#include "railroad.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
LL plan_roller_coaster(vector<int> s, vector<int> t){
int n=SZ(s);
LL dp[(1LL<<n)][n][n];
FOR(i,(1LL<<n)) FOR(j,n) FOR(k,n) dp[i][j][k]=1e18;
FOR(i,n) dp[(1LL<<i)][i][i]=0;
for (LL msk=1; msk<(1LL<<n); msk++){
if (__builtin_popcount(msk)==1) continue;
FOR(i,n) FOR(j,n){
if (msk&(1LL<<i) && msk&(1LL<<j) && i!=j){
LL res=1e18;
LL omsk=msk^(1LL<<j);
FOR(k,n) if (omsk&(1LL<<k)){
if (dp[omsk][i][k]==1e18) continue;
//cout<<"i: "<<i<<", j: "<<j<<", k: "<<k<<", omsk: "<<omsk<<", dp: "<<dp[omsk][i][k]<<"\n";
res=min(res, dp[omsk][i][k]+max(t[k]-s[j],0));
}
dp[msk][i][j]=res;
}
}
}
LL ans=1e18;
FOR(i,n) FOR(j,n) if (dp[(1LL<<n)-1][i][j]!=1e18) ans=min(ans, dp[(1LL<<n)-1][i][j]);
return ans;
}
