


#include <bits/stdc++.h>

#define loop(s, e, i) for (int i = s; i < e; ++i)
#define print(s) cout << s << endl;
#define DIV 1000000007
#define ll long long
using namespace std;

const int INF = 1e9+7;

int show_matrix(vector<vector<int>> &dp) {
  loop(0, dp.size(), i) {
    loop(0, dp[i].size(), j) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}

/*
浮動小数点の入力
cout << fixed << setprecision(9) << endl;
*/

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  ll N;
  cin >> N;

  vector<ll> X(N);
  vector<ll> Y(N);
  vector<ll> Z(N);

  loop(0, N, i) {
    cin >> X[i];
    cin >> Y[i];
    cin >> Z[i];
  }

  vector<vector<ll>> DP(N, vector<ll>(1 << N, INF));
  DP[0][1] = 0;

  for (ll bit=1; bit < (1 << N); bit++) {
    loop(0, N, i) {
      ll next_bit = bit | (1 << i);
      loop(0, N, j) {
        ll cost = abs(X[i] - X[j]) + abs(Y[i] - Y[j]) + max((ll)0, Z[j] - Z[i]);
        DP[j][next_bit] = min(DP[j][next_bit], DP[i][bit] + cost);
      }
    }
  }
  ll complete = (1 << N) - 1;
  print(DP[0][complete]);
}

#include<bits/stdc++.h>
using namespace std;
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
typedef long long ll;

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	for(ll i = 0; i < n; i++) cin >> a[i];
	sort(a.rbegin(), a.rend());
	vector<ll> pref(n, 0);
	pref[0] = a[0];
	for(ll i = 1; i < n; i++) {
		pref[i] = pref[i-1] + a[i];
	}
	ll ans = 0;
	for(ll i = 0; i < n-1; i++) {
		ans += (n-i-1) * a[i] - (pref[n-1] - pref[i]);
	}
	cout << ans << endl;
}