#include<bits/stdc++.h>
using namespace std;
#include "railroad.h"
int mk[10];
long long resp=1123456789123456789;
void bk(int n,int k,vector<int> e,vector<int> s,int ant,long long at)
{
if(k==n)resp=min(resp,at);
for(int i=0;i<n;i++)
{
if(mk[i]==0)
{
long long vl=0;
if(k>0)
{
vl=max(s[ant]-e[i],0);
}
mk[i]=1;
bk(n,k+1,e,s,i,at+vl);
mk[i]=0;
}
}
}
long long plan_roller_coaster(vector<int> e,vector<int> s)
{
int n=e.size();
bk(n,0,e,s,-1,0);
return resp;
}
/*int main()
{
int n;
scanf("%d",&n);
vector<int> e,s;
for(int i=0;i<n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
e.push_back(a);s.push_back(b);
}
printf("%lld\n",plan_roller_coaster(e,s));
return 0;
}*/
