#include "railroad.h"
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
const ll INF = 1e18;
vector<ll> S, T;
int N; ll dp[(1<<17)][17];
ll solve(int msk, int j) {
if(__builtin_popcount(msk) == N+1) return 0;
ll& ret = dp[msk][j];
if(ret != -1) return ret;
ret = 1e18;
for(int i=0; i<=N; i++) {
if((msk & (1<<i)) != 0) continue;
int nmsk = msk | (1<<i);
ll s = max((ll)0, T[j] - S[i]);
ret = min(ret, s + solve(nmsk, i));
}
return ret;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
N = (int)s.size();
S = T = vector<ll>(1, 0);
for(int i=0; i<N; i++) {
S.push_back(s[i]);
T.push_back(t[i]);
}
memset(dp, -1, sizeof(dp));
return solve(1, 0);
}
