#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=2e5+5;
int n;
pii p[N];
ll dp[(1<<16)+5][17];
ll rek(int mask, int pr) {
int siz=__builtin_popcount(mask);
if (siz==n) return 0;
ll &ret=dp[mask][pr];
if (ret!=-1) return ret;
ret=MAX;
for (int i=0; i<n; ++i) {
if (mask & (1<<i)) continue;
ret=min(ret, rek(mask | (1<<i), i)+max(p[pr].Y-p[i].X, 0));
}
return ret;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
n=s.size();
for (int i=0; i<n; ++i) p[i]=mp(s[i], t[i]);
p[n]=mp(0, 1);
memset(dp, -1, sizeof dp);
ll sol=rek(0, n);
return sol;
}
