#include "railroad.h"
#include <bits/stdc++.h>
#define INF 10000000000000009ll
using namespace std;
typedef long long ll;
int n;
ll memo[17][(1<<16)+10];
vector<int> a,b;
ll dp(int i, int bitmask){
if(bitmask==((1<<n)-1)){
//printf("test\n");
return memo[i][bitmask]=0ll;
}
if(memo[i][bitmask]!=-1ll){
return memo[i][bitmask];
}
//printf("%d %d\n",i,bitmask);
memo[i][bitmask]=INF;
for(int x=0;x<n;x++){
if(((1<<x)&bitmask)==0){
memo[i][bitmask]=min(memo[i][bitmask],dp(x,bitmask|(1<<x))+max(0ll,(ll)b[i]-a[x]));
}
}
return memo[i][bitmask];
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
n = (int) s.size();
//printf("%d\n",n);
a=s,b=t;
for(int x=0;x<n;x++){
for(int y=0;y<=(1<<n);y++)
memo[x][y]=-1ll;
}
ll ans=INF;
for(int x=0;x<n;x++)
ans=min(ans,dp(x,(1<<x)));
return ans;
}
