#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int Nmax = 17;
int n, start[Nmax], finish[Nmax];
ll dp[1<<Nmax][Nmax];
ll solve1(vector<int> &start, vector<int> &finish)
{
int i, j, k;
for(i=0; i<(1<<n); ++i)
for(j=0; j<n; ++j)
dp[i][j] = inf;
for(i=0; i<n; ++i) dp[1<<i][i] = 0;
for(i=1; i<(1<<n); ++i)
for(j=0; j<n; ++j)
if(i&(1<<j))
for(k=0; k<n; ++k)
if(!(i&(1<<k)))
dp[i^(1<<k)][k] = min(dp[i^(1<<k)][k], dp[i][j] + max(0, finish[j] - start[k]));
ll ans = inf;
for(j=0; j<n; ++j) ans = min(ans, dp[i-1][j]);
return ans;
}
ll plan_roller_coaster(vector<int> s, vector<int> t)
{
n = s.size();
int i;
for(i=1; i<=n; ++i) start[i] = s[i-1], finish[i] = t[i-1];
if(n <= 16) return solve1(s, t);
return 0;
}
