//#include "railroad.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
#define INF 1000000000000000000LL
using namespace std;
int n;
vector< pair<int, int> > speeddat;
long long int dptable[17][(1 << 16) - 1];
int LSOne(int i) {
return i & (-i);
}
int logtwo(int i) {
int ans = 0;
while (i) {
ans += 1;
i >>= 1;
}
return ans;
}
long long int speeddp(int sp, int mask) {
if (mask == 0) return 0;
if (dptable[sp][mask] != -1) return dptable[sp][mask];
long long int ans = INF;
int temp = mask;
while (temp) {
int X = LSOne(temp);
if (sp == 0) {
ans = min(ans, speeddp(speeddat[logtwo(X) - 1].first, mask & (~X)));
} else {
ans = min(ans, speeddp(speeddat[logtwo(X) - 1].first, mask & (~X)) + max(0, speeddat[sp - 1].first - speeddat[logtwo(X) - 1].first));
}
temp = temp & (~X);
}
return dptable[sp][mask] = ans;
}
long long int plan_roller_coaster(vector<int> s, vector<int> t) {
n = s.size();
for (int i = 0; i < n; i++) {
speeddat.push_back(make_pair(t[i], s[i]));
}
if (n > 16) {
return 0;
} else {
memset(dptable, -1, sizeof(dptable));
return speeddp(0, (1 << n) - 1);
}
}
