/**
 * Solution to Pokemon Go.
 *
 * Again, with handbook TSP code (no changes needed this time).
 * We compute the full O(2^20 * 20) stops for around ~20M ops.
 *
 * @author godmar
 */
import java.util.*;
import static java.lang.Math.*;
import java.util.function.Function; // Java 8 and up

public class PokeMonGodmar {
    public static void main(String []av) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        final Stop start = new Stop(0, 0);
        final Map<Stop, Integer> stops2No = new HashMap<>();
        final Stop [] stops = new Stop[n];
        int stopCount = 0;

        final Map<String, Integer> pokemons = new HashMap<>();
        int pokeMonCount = 0;
        int [] findAtStops = new int[20];
        for (int i = 0; i < n; i++) {
            // index stops
            Stop loc = new Stop(s.nextInt(), s.nextInt());
            Integer stopNo = stops2No.get(loc);
            if (stopNo == null) {
                stopNo = stopCount;
                stops2No.put(loc, stopCount++);
                stops[stopNo] = loc;
            }

            // index pokemons
            String pokemon = s.next();
            Integer pokeMonNo = pokemons.get(pokemon);
            if (pokeMonNo == null) {
                pokeMonNo = pokeMonCount;
                pokemons.put(pokemon, pokeMonCount++);
            }
            findAtStops[stopNo] |= (1 << pokeMonNo);
        }

        TSP tsp = new TSP(stopCount) {
            int dist(int from, int to) {
                return stops[from].manhattanDistance(stops[to]);
            }

            int initialdist(int to) {
                return start.manhattanDistance(stops[to]);
            }
        };

        int [][] dp = tsp.solve();

        // a "full tour" may occur without visiting all stops
        // as long we have all pokemons.
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < dp.length; i++) {
            int found = 0;
            for (int j = 0; j < stopCount; j++) if (((1 << j) & i) != 0)
                found |= findAtStops[j];

            // did I catch all?
            if (found != (1 << pokeMonCount) - 1)
                continue;

            for (int j = 0; j < dp[i].length; j++)
                best = Math.min(best, dp[i][j] + stops[j].manhattanDistance(start));
        }

        System.out.println(best);
    }

    static class Stop {
        final int r, c;
        Stop(int r, int c) {
            this.r = r;
            this.c = c;
        }

        int manhattanDistance(Stop that) {
            return abs(this.r - that.r) + abs(this.c - that.c);
        }

        @Override
        public int hashCode() { return 100*r + c; }
        @Override
        public boolean equals(Object _that) {
            Stop s = (Stop)_that;
            return r == s.r && c == s.c;
        }
        @Override
        public String toString() {
            return r + " " + c;
        }
    }

    /* A TSP Solver.  */
    static abstract class TSP {
        int n;
        TSP(int n)  { this.n = n; }

        /* distance from node 'from' to node 'to'.
         * Must return zero if from == to. */
        abstract int dist(int from, int to);

        /* initial cost when starting in point 'start';
         * set to inf if node is not allowed as start point */
        abstract int initialdist(int to);

        /* return array B[i] of lengths of optimal tour ending in node i,
         * including any initial cost to reach the starting point when
         * pursuing the optimal tour. */
        int[][] solve() {
            // precompute and cache distances to avoid calls
            // to dist() in inner loop
            final int [][]D = new int[n][n];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    D[j][i] = dist(j, i);

            int[][] dp = new int[1 << n][n];
            for (int[] row : dp)
                Arrays.fill(row, Integer.MAX_VALUE/2);

            for (int i = 0; i < n; i++)
                dp[1<<i][i] = initialdist(i);

            for (int mask = 0; mask < 1 << n; mask++)
                for (int i = 0; i < n; i++)
                    if ((mask & 1 << i) > 0)
                        for (int j = 0; j < n; j++)
                            if (i != j && (mask & 1 << j) > 0)
                                dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1<<i)][j] + D[j][i]);

            return dp;
        }
    }
}