#include <bits/stdc++.h>
#include <math.h>

using namespace std;

template<typename T>
long long modpow(const T n,const T p,const T mod);
template<typename T>
long long modinv(const T n,const T mod);
template<typename T>
bool chmax(T &a,const T &b);
template<typename T>
bool chmin(T &a,const T &b);

long long inf=1000000007;

int main(){
	long long n;
	cin>>n;
	vector<vector<long long>> tosi(n,vector<long long>(3));

	for(long long i=0;i<n;i++) cin>>tosi.at(i).at(0)>>tosi.at(i).at(1)>>tosi.at(i).at(2);
	vector<vector<long long>> dp(n,vector<long long>(modpow((long long)2,n,inf),inf));
	dp.at(0).at(0)=0;

	for(long long i=0;i<(1<<n);i++){
		bitset<18> bits=i;
		for(long long j=0;j<n;j++){
			if(!(i==0 && j==0) && bits.test(j)==false) continue;
			for(long long k=0;k<n;k++){
				if(bits.test(k)) continue;

				long long a=abs(tosi.at(j).at(0)-tosi.at(k).at(0));
				long long b=abs(tosi.at(j).at(1)-tosi.at(k).at(1));
				long long c=max((long long)0,tosi.at(k).at(2)-tosi.at(j).at(2));
				chmin(dp.at(k).at(i+modpow((long long)2,k,inf)),dp.at(j).at(i)+a+b+c);
			}
		}
	}

	cout<<dp.at(0).at(modpow((long long)2,n,inf)-1)<<endl;

	return 0;
}

template<typename T>
long long modpow(const T n,const T p,const T mod){
	if(p==0) return 1;
	if(p%2==0){
		long long a=modpow(n,p/2,mod);
		return a*a%mod;
	}
	if(p%2==1) return (modpow(n,p-1,mod)*n)%mod;
	cerr<<"ERROR"<<endl;
	return 1;
}

template<typename T>
long long modinv(const T n,const T mod){
	return modpow(n,mod-2,mod);
}

template<typename T>
bool chmax(T &a,const T &b){
	if(a<b){
		a=b;
		return 1;
	}
	return 0;
}

template<typename T>
bool chmin(T &a,const T &b){
	if(a>b){
		a=b;
		return 1;
	}
	return 0;
}

#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
int a,b,c,d;
int main () {
#ifndef ONLINE_JUDGE
file("e");
#endif
	a=read();
	b=read();
	c=read();
	d=read();
	printf("%d\n",a*d-b*c);
	return 0;
}
