#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e18;
vpll d;
ll n;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = s.size();
d.resize(n);
loop(i,0,n) {
d[i] = {s[i], t[i]};
}
vvll dp(1LL<<n,vll(3,inf)); //mask - > dpval, l ,r;
dp[0][0] = 0;
loop(i,0,n) {
dp[(1LL<<i)][0] = 0;
dp[(1LL<<i)][1] = d[i].first;
dp[(1LL<<i)][2] = d[i].second;
}
loop(mask, 1,1LL<<n) {
ll l1 = dp[mask][1] , r1 = dp[mask][2];
ll val = dp[mask][0];
loop(i,0,n) {
if (!(mask&(1LL<<i))) {
ll l = d[i].first, r = d[i].second;
ll& dpval = dp[mask^(1LL<<i)][0];
if (dpval > val + max(0LL, r1-l)) {
dpval = val + max(0LL, r1-l);
dp[mask^(1LL<<i)][1] = l1;
dp[mask^(1LL<<i)][2] = r;
}
if (dpval > val + max(0LL, r-l1)) {
dpval = val + max(0LL, r-l1);
dp[mask^(1LL<<i)][1] = l;
dp[mask^(1LL<<i)][2] = r1;
}
}
}
}
ll full = (1LL<<n)-1;
return dp[full][0];
}
