#include "railroad.h"
#include <cstdio>
#include <cassert>
#include "railroad.h"
#include <bits/stdc++.h>
#define INF LLONG_MAX
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
using namespace std;
int n;
vector<int> li,exi;
long long dp[1<<17];
long long solve(long long speed,long long idx,long long rails,int state){
//debug(rails);
//debugs(speed,idx);
if(idx==n)
return rails;
if(dp[state]!=-1)
return dp[state];
long long ans=INF;
for (int i = 0; i < n; ++i)
{
if((state&(1<<i))==0){
//debug(i);
ans=min(ans,solve(exi[i],idx+1,rails+max(0LL,speed-li[i]),(state|(1<<i))));
}
}
return dp[state]=ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
memset(dp,-1,sizeof dp);
n = (int) s.size();
li=s;
exi=t;
return solve(1,0,0,0);
}
