#include <bits/stdc++.h>
using namespace std;


//TEMPLATE
#define len(a)            (ll) a.size()
#define ms(a, x)          memset(a, x, sizeof a)
#define bitcount(n)       __builtin_popcountll(n)
#define FR                ios_base::sync_with_stdio(false);cin.tie(NULL)

#define cin1(a)           cin >> a
#define cin2(a, b)        cin >> a >> b
#define cin3(a, b, c)     cin >> a >> b >> c
#define cin4(a, b, c, d)  cin >> a >> b >> c >> d
#define cots(a)           cout << a << " "
#define cot1(a)           cout << a << "\n"
#define cot2(a, b)        cout << a << " " << b << "\n"
#define cot3(a, b, c)     cout << a << " " << b << " " << c << "\n"
#define cot4(a, b, c, d)  cout << a << " " << b << " " << c << " " << d << "\n"
#define cotcase(cs)       cout << "Case " << cs << ": "
#define yes               cout << "Yes\n"
#define no                cout << "No\n"
#define line              cout << "\n"

#define reversed(s)       reverse(s.begin(), s.end())
#define asort(s)          sort(s.begin(), s.end())
#define dsort(s)          sort(s.rbegin(), s.rend())
#define all(s)            s.begin(), s.end()
#define uniq(s)           s.resize(distance(s.begin(),unique(s.begin(), s.end())))
#define found(s, x)       (s.find(x) != s.end())

#define for0(i, n)        for (i = 0; i < n; i++)
#define for1(i, n)        for (i = 1; i <= n; i++)
#define fora(i, a, b)     for (i = a; i <= b; i++)
#define forb(i, b, a)     for (i = b; i >= a; i--)

#define ll                long long
#define pb                push_back
#define mp                make_pair
#define ld                long double
#define pii               pair <ll, ll>
#define piii              pair <ll, pii>
#define F                 first
#define S                 second
#define pi                acos(-1)

const ll INF = LLONG_MAX;
const ll SZ = 17;
const ll mod = 1e9+7;



string s, s1, s2;
ll n, k, ans = 0;
ll a[SZ];
//ll b[SZ];

struct dat {
    ll x, y, z;
} ct[SZ];
ll dp[20][(1LL<<SZ)+5];

bool check(ll x, ll pos) {
    return (x & (1LL << pos));
}

ll set1(ll x, ll pos) {
    return (x = x | (1LL << pos));
}

ll cal(dat c1, dat c2) {
    ll d = abs(c1.x - c2.x) + abs(c1.y - c2.y) + max(0LL, c2.z-c1.z);
    return d;
}

ll solve(ll in, ll msk) {
    if(bitcount(msk) == n) return cal(ct[in], ct[0]);
    ll i, t, &res = dp[in][msk];
    if(res != -1) return res;
    res = INF;

    for0(i, n) {
        if(check(msk, i)) continue;
        t = cal(ct[in], ct[i]) + solve(i, set1(msk, i));
        res = min(res, t);
    }

    return res;
}

int main() {
    FR;
    ll cs = 0, tc = 1, x, y, z, i, j, g, p, q, sum = 0, c = 0, t = 0;
//    ll a, b, d;
//    string s, s1, s2;

    cin1(n);
    for0(i, n) cin3(ct[i].x, ct[i].y, ct[i].z);

    ms(dp, -1);
    cot1(solve(0, 1));

    return 0;
}


//ll min_len[1<<8];
//void __(){
//    _(ll,n);
//    _(ll,m);
//    _(vl,a,n);
//    _(vpll,b,m);
//    rep(bm,1<<n){
//        ll w = 0;
//        rep(i,n)
//            if(bm&(1<<i))
//                w += a[i];
//        rep(i,m){
//            if(b[i].Y < w)
//                min_len[bm] = max(min_len[bm],b[i].X);
//        }
//    }
//    rep(i,n)
//        if(min_len[1<<i] != 0){
//            print -1;
//            return;
//        }
//    vi order(n);
//    iota(all(order),0);
//    ll ans = INF;
//    do{
//        vl x(n);
//        rep(i,1,n-1){
//            x[i] = x[i-1];
//            ll bm = 1<<order[i];
//            per(j,i){
//                bm |= 1<<order[j];
//                x[i] = max(x[i],min_len[bm]+x[j]);
//            }
//        }
//        ans = min(ans,x.back());
//    }while(next_permutation(all(order)));
//    print ans;
//}
//
#include <numeric>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define REP_INT(i,l,r) for(int i = (l); i <= (r); ++i)
#define REP_ZERO_INT(i,r) for(int i = 0; i < (r); ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define PER_ZERO_INT(i,r) for(int i = (r)-1; i >= 0; --i)
#define GET_PER_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define per(...) GET_PER_MACRO(__VA_ARGS__,PER_ANY,PER_INT,PER_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define X first
#define Y second
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
const ll INF = ll(2e18) + 666;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
template <typename F, typename S> static
istream& operator>>(istream& stream, pair<F, S>& t){
    return stream >> t.first >> t.second;
}
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout) 
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }

    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
#define INPUT_WITHOUT_INIT(type,name) type name; cin >> name
#define _IWI(type,name,...) type name(__VA_ARGS__); cin >> name
#define GET_INPUT_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define _(...) GET_INPUT_MACRO(__VA_ARGS__,_IWI,_IWI,_IWI,_IWI,_IWI,_IWI,INPUT_WITHOUT_INIT)(__VA_ARGS__)
ll min_len[1<<8];
void __(){
    _(ll,n);
    _(ll,m);
    _(vl,a,n);
    _(vpll,b,m);
    rep(bm,1<<n){
        ll w = 0;
        rep(i,n)
            if(bm&(1<<i))
                w += a[i];
        rep(i,m){
            if(b[i].Y < w)
                min_len[bm] = max(min_len[bm],b[i].X);
        }
    }
    rep(i,n)
        if(min_len[1<<i] != 0){
            print -1;
            return;
        }
    vi order(n);
    iota(all(order),0);
    ll ans = INF;
    do{
        vl x(n);
        rep(i,1,n-1){
            x[i] = x[i-1];
            ll bm = 1<<order[i];
            per(j,i){
                bm |= 1<<order[j];
                x[i] = max(x[i],min_len[bm]+x[j]);
            }
        }
        ans = min(ans,x.back());
    }while(next_permutation(all(order)));
    print ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}

