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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
using LD = long double;

template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <typename T> void coutall(T v) { if(v.empty()){cout << endl; return;} for(auto i = v.begin(); i != --v.end(); i++){cout << *i << " ";} cout << *--v.end() << endl; }
void yes(bool ok = true){ cout << (ok ? "yes" : "no") << endl; }
void Yes(bool ok = true){ cout << (ok ? "Yes" : "No") << endl; }
void YES(bool ok = true){ cout << (ok ? "YES" : "NO") << endl; }
ll myceil(ll a, ll b) { return a >= 0 ? (a+b-1)/b : -((-a)/b); }
ll myfloor(ll a, ll b) { return a >= 0 ? a/b : -myceil(-a, b); }

int keta(ll x){
    int res = 0;
    while(x){
        x /= 10;
        res++;
    }    
    return res;
}

void Main(){
    ll n; cin >> n;
    if(n < 1000){
        cout << 0 << endl;
        return;
    }
    int k = keta(n);
    ll p = pow(10ll, k-1);
    ll t = n / p;
    ll ans = ((n % p) + 1) * ((k-1)/3);
    ans += (t-1) * p * ((k-1)/3);
    //cout << k << " " << ans << endl;
    for(ll i = k-1; i >= 4; i--){
        ans += ll((i-1)/3) * 9 * pow(10ll, i-1);
        //cout << i << " " << ll((i-1)/3) * 9 * pow(10ll, i-1) << endl;
    }
    cout << ans << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}
// clang-format off
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;
using namespace __gnu_pbds;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
// clang-format on

int n;
int x[17], y[17], z[17];

int dist(int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0, z[j] - z[i]);
}

int main() {
    fastio();

    cin >> n;
    forn(i, n) cin >> x[i] >> y[i] >> z[i];

    vec<vi> dp(1 << n, vi(n, INT_MAX));
    dp[1][0] = 0;

    forn1(sz, n - 1) {
        int s = (1 << sz) - 1;
        while (s < 1 << n) {
            forn(last, n) {
                int c = dp[s][last];
                if (c == INT_MAX) continue;
                forn(next, n) {
                    if (last == next) continue;

                    if ((s >> next) & 1) continue;

                    int x = c + dist(last, next);

                    if (sz == n - 1) {
                        x += dist(next, 0);
                    }

                    auto t = s | (1 << next);
                    chmin(dp[t][next], x);
                }
            }

            int x = s & -s, y = s + x;
            s = ((s & ~y) / x >> 1) | y;
        }
    }

    int ans = INT_MAX;
    forn(i, n) {
        chmin(ans, dp[(1 << n) - 1][i]);
    }

    cout << ans << endl;
    return 0;
}
