#include <bits/stdc++.h>
#define N 1000005
#define ll long long int
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
#include "railroad.h"
using namespace std;
ll n,m,ar[N],sum,t,pw[N];
ll dp[20][70000];
ii p[N];
ll f(ll ind,ll mask)
{
if(mask==pw[n]-1)
return 0;
if(dp[ind][mask]!=-1)
return dp[ind][mask];
ll top=1e18;
fo(i,0,n-1)
{
if((mask & pw[i]))
continue;
ll x=(mask | pw[i]);
top=min(top,f(i,x) + max(0,p[ind].se-p[i].fi));
}
// cout<<"[d]"<<sp<<ind<<sp<<mask<<sp<<top<<endl;
return dp[ind][mask]=top;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = (int) s.size();
memset(dp,-1,sizeof(dp));
pw[0]=1;
fo(i,1,20)
pw[i]=pw[i-1]*2;
fo(i,0,t.size()-1)
if(t[i]==0)
return 0;
fo(i,0,s.size()-1)
if(s[i]==0)
return 0;
fo(i,0,n-1)
p[i]={s[i],t[i]};
ll x=1e18;
fo(i,0,n-1)
x=min(x,f(i,pw[i]));
return x;
// return 1;
}
// vector<int> a,b;
// int main()
// {
// fast;
// cin>>n;
// fo(i,1,n)
// {
// int x,y;
// cin>>x>>y;
// a.pb(x);
// b.pb(y);
// }
// cout<<plan_roller_coaster(a,b);
// }
