#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long un;
typedef vector<un> vuc;
#define REP(i, a, b) for(un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
constexpr un INF = INT64_MAX;
un compute(vec<int> s, vec<int> t, vuc perm){
un ret = 0;
REP(i, 0, perm.size()-1){
ret += max(0, t[perm[i]] - s[perm[i+1]]);
}
return ret;
}
un easy(std::vector<int> s, std::vector<int> t, un N){
vuc perm(N);
iota(ALL(perm), 0);
un ret = INF;
do{
ret = min(ret, compute(s, t, perm));
} while(next_permutation(ALL(perm)));
return ret;
}
vuc compute_ends(std::vector<int> s, std::vector<int> t, vuc toUse, un N){
vuc tab(N, -1);
REP(i, 0, toUse.size()){
tab[toUse[i]] = i;
}
sort(ALL(toUse));
vuc ret(toUse.size(), INF);
do{
ret[tab[toUse[toUse.size()-1]]] = min(ret[tab[toUse[toUse.size()-1]]], compute(s, t, toUse));
} while(next_permutation(ALL(toUse)));
return ret;
}
vuc compute_starts(std::vector<int> s, std::vector<int> t, vuc toUse, un N){
vuc tab(N, -1);
REP(i, 0, toUse.size()){
tab[toUse[i]] = i;
}
sort(ALL(toUse));
vuc ret(toUse.size(), INF);
do{
ret[tab[toUse[0]]] = min(ret[tab[toUse[0]]], compute(s, t, toUse));
} while(next_permutation(ALL(toUse)));
return ret;
}
un meet_in_mid(std::vector<int> s, std::vector<int> t, un N){
un ret = INF;
vuc A;
vuc B;
REP(i, 0, 1<<N){
if (__builtin_popcountll(i) != (N/2)) continue;
REP(j, 0, N){
if (i & (1 << j)) A.push_back(j);
else B.push_back(j);
}
vuc A_ret = compute_ends(s, t, A, N);
vuc B_ret = compute_starts(s, t, B, N);
REP(x, 0, A.size()) REP(y, 0, B.size()) {
ret = min(ret, A_ret[x] + B_ret[y] + max(0, t[A[x]] - s[B[y]]));
}
A.clear();
B.clear();
}
return ret;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
un N = (un) s.size();
// if (N <= 8) return easy(s, t, N);
if (N <= 16) return meet_in_mid(s, t, N);
return 0;
}
