#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
//#include "railroad.h"
const ll inf = 1e18;
int n;
vt<ll>s, t;
ll dp[(1 << 16)][16];
void ckmin(ll &a, ll b){
if(a > b)a = b;
}
ll sub12(){
for(int i = 0; i < (1 << n); i++){
for(int j = 0; j < n; j++){
dp[i][j] = inf;
}
}
for(int i = 0; i < n; i++){
dp[(1 << i)][i] = 0;
}
for(int i = 1; i < (1 << n); i++){
for(int j = 0; j < n; j++){
//cout << i << " " << j << " " << dp[i][j] << "\n";
if((i >> j) & 1){
for(int k = 0; k < n; k++){
if(!((i >> k) & 1)){
ckmin(dp[i ^ (1 << k)][k], dp[i][j] + max(t[j] - s[k], (ll)0));
}
}
}
}
}
ll ans = inf;
for(int i = 0; i < n; i++){
ckmin(ans, dp[(1 << n) - 1][i]);
}
return(ans);
}
long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
for(auto i: S)s.pb(i);
for(auto i: T)t.pb(i);
n = sz(s);
if(n <= 16){
return(sub12());
}
return 0;
}
/*
#include <cstdio>
#include <cassert>
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}
*/
