#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // int64_t
using ull = unsigned long long;
using pii = pair<int,int>;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)

const ll INF = 1e9+7;   //10oku7


int N;
vector<vector<ll>> dist;
vector<vector<ll>> dp;

ll binary(ll x){
    ll ans = 0;
    ll count = 0;
    while ( x >0 ){
      ans = ans + (x%2)*pow(10ll,count);
      x /= 2;
      count ++;
    }
    return ans;
}

ll rec(ll bits, ll j ){
  if (dp.at(bits).at(j) < INF*2) return dp.at(bits).at(j);
  if (bits == 0 && j == 0) return 0;
  if (!((bits >> j ) & 1 )) {
    dp.at(bits).at(j) = INF;
    return INF;
  }
  rep(i,N){
    if ( bits == 1<<i ){
      dp.at(bits).at(i) = dist.at(0).at(j);
      return dp.at(bits).at(i);
    }
  }
  ll temp = INF;

  rep(i,N){
    if (((bits >> i ) & 1) ){
//      cout << binary(bits) << " " << i << endl;
      temp = min (temp, rec(bits - (1<<j), i) + dist.at(i).at(j));
    }
  }

  dp.at(bits).at(j) = temp;
  return temp;
}

int main() {
  cin >> N;
  vector<ll> X(N);
  vector<ll> Y(N);
  vector<ll> Z(N);
  rep(i,N){
    cin >> X.at(i) >> Y.at(i) >> Z.at(i);
  }

  dist = vector<vector<ll>> (N,vector<ll>(N,INF));
  dp = vector<vector<ll>> ((1 << N) ,vector<ll>(N,INF*2));


  rep(i,N){
    rep (j,N){
      dist.at(i).at(j) = abs (X.at(i) - X.at(j) ) + abs( Y.at(i) - Y.at(j)) + max (0ll, Z.at(j) - Z.at(i));
    }
  }

  cout << rec ((1<<N) -1,0) << endl;

}

#include "cstdio"
#include "cstring"
#include "cctype"
#include "queue"
#define R register
#define getchar() (_==__&&(__=(_=___)+fread(___,1,1<<16,stdin),_==__)?EOF:*_++)
char ___[1<<16],*_=___,*__=___;
const int big=100010;
int n;
long long ans,a[big];
std::priority_queue<int>q[2];
inline int read()
{
    char c(getchar());int x(0),f(1);
    for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
    for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
    return f*x;
}
int main(void)
{
    // freopen("data.in","r",stdin);
    n=read();
    for(R int i(1);i<=n;++i)a[i]=read(),ans+=a[i];
    for(R int i(1);i<=n;++i)q[i&1].push(read()-a[i]);
    while(!q[0].empty()&&!q[1].empty()&&q[0].top()+q[1].top()>0)ans+=q[0].top()+q[1].top(),q[0].pop(),q[1].pop();
    printf("%lld\n",ans);
    end:return 0;
}