#include "railroad.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <utility>
using namespace std;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int N = (int) s.size();
vector<vector<long long> > bestDP ((1 << N) + 1, vector<long long> (N, ((long long) 1 << 62)));
for (int i = 0; i < N; i++){
bestDP[(1 << i)][i] = 0;
//cout << s[i] << ' ' << t[i] << endl;
}
for (long long rails = 1; rails < (1 << N); rails++){
for (long long last = 0; last < N; last++){
if (rails & (1 << last)){
for (int second_last = 0; second_last < N; second_last++){
bestDP[rails][last] = min(bestDP[rails][last], bestDP[rails ^ (1 << last)][second_last] + max(0, t[second_last] - s[last]));
//cout << ' ' << rails << ' ' << last << ' ' << second_last << ' ' << bestDP[rails ^ (1 << last)][second_last] << ' ' << t[second_last] << ' ' << s[last] << endl;
}
}
//cout << bestDP[rails][last] << ' ' << rails << ' ' << last << endl;
}
}
long long best = ((long long) 1 << 62);
for (int i = 0; i < N; i++){
best = min(best, bestDP[(1 << N) - 1][i]);
//cout << bestDP[(1 << N) - 1][i] << endl;
}
return best;
}
