import java.io.BufferedReader;
import java.io.FileReader;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Euler424 {
    static final int LETTERS = 10;
    static final int MAX_LEN = 9;
    static final int MAX_SUM = 45;
    static final int LETTER_MASK = (1 << LETTERS) - 1;
    static final int CELL_MASK = LETTER_MASK & ~1;

    @SuppressWarnings("unchecked")
    static List<Long>[][] tupleCodes = new List[MAX_LEN + 1][MAX_SUM + 1];

    static {
        for (int i = 0; i <= MAX_LEN; i++) {
            for (int j = 0; j <= MAX_SUM; j++) {
                tupleCodes[i][j] = new ArrayList<>();
            }
        }
    }

    static int popcount(int x) {
        return Integer.bitCount(x);
    }

    static boolean isSingle(int x) {
        return x != 0 && (x & (x - 1)) == 0;
    }

    static int singleValue(int x) {
        return Integer.numberOfTrailingZeros(x);
    }

    static void genTuples(int len, int pos, int usedMask, int sum, long code) {
        if (pos == len) {
            tupleCodes[len][sum].add(code);
            return;
        }
        for (int d = 1; d <= 9; d++) {
            if ((usedMask & (1 << d)) != 0)
                continue;
            genTuples(len, pos + 1, usedMask | (1 << d), sum + d, code | ((long) d << (4 * pos)));
        }
    }

    static void prepareTuples() {
        if (!tupleCodes[1][1].isEmpty())
            return;
        for (int len = 1; len <= MAX_LEN; len++) {
            genTuples(len, 0, 0, 0, 0L);
        }
    }

    static class Run {
        List<Integer> cells = new ArrayList<>();
        int[] clueLetters = new int[2];
        int clueLen = 0;
    }

    static class Puzzle {
        int n = 0;
        int[] whiteIndex;
        List<Integer> cellLetter = new ArrayList<>();
        List<Run> runs = new ArrayList<>();
    }

    static class State {
        int[] letterDom = new int[LETTERS];
        int[] cellDom;

        State(int size) {
            Arrays.fill(letterDom, LETTER_MASK);
            cellDom = new int[size];
            Arrays.fill(cellDom, CELL_MASK);
        }

        State copy() {
            State n = new State(this.cellDom.length);
            System.arraycopy(this.letterDom, 0, n.letterDom, 0, LETTERS);
            System.arraycopy(this.cellDom, 0, n.cellDom, 0, this.cellDom.length);
            return n;
        }
    }

    static List<String> splitCsv(String line) {
        List<String> out = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        int depth = 0;
        for (char ch : line.toCharArray()) {
            if (ch == ',' && depth == 0) {
                out.add(cur.toString());
                cur.setLength(0);
            } else if (ch != ' ' && ch != '\r' && ch != '\n' && ch != '\t') {
                cur.append(ch);
                if (ch == '(')
                    depth++;
                else if (ch == ')')
                    depth--;
            }
        }
        out.add(cur.toString());
        return out;
    }

    static int letterId(char ch) {
        if (ch >= 'A' && ch <= 'J')
            return ch - 'A';
        return -1;
    }

    static boolean isWhiteToken(String tok) {
        if (tok.equals("O"))
            return true;
        return tok.length() == 1 && letterId(tok.charAt(0)) != -1;
    }

    static Puzzle parsePuzzleLine(String line) {
        List<String> tokens = splitCsv(line);
        if (tokens.isEmpty())
            return null;
        int n = 0;
        try {
            n = Integer.parseInt(tokens.get(0));
        } catch (Exception e) {
            return null;
        }
        if (n <= 0 || tokens.size() != 1 + n * n)
            return null;

        List<String> grid = tokens.subList(1, tokens.size());
        Puzzle puzzle = new Puzzle();
        puzzle.n = n;
        puzzle.whiteIndex = new int[n * n];
        Arrays.fill(puzzle.whiteIndex, -1);

        int whiteCount = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                String tok = grid.get(r * n + c);
                if (!isWhiteToken(tok))
                    continue;
                puzzle.whiteIndex[r * n + c] = whiteCount++;
                if (tok.equals("O"))
                    puzzle.cellLetter.add(-1);
                else
                    puzzle.cellLetter.add(letterId(tok.charAt(0)));
            }
        }

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                String tok = grid.get(r * n + c);
                if (tok.length() < 2 || tok.charAt(0) != '(' || tok.charAt(tok.length() - 1) != ')')
                    continue;
                String inside = tok.substring(1, tok.length() - 1);
                String[] parts = inside.split(",");
                for (String part : parts) {
                    if (part.length() < 2)
                        return null;
                    boolean horiz = part.charAt(0) == 'h';
                    if (!horiz && part.charAt(0) != 'v')
                        return null;

                    String clueStr = part.substring(1);
                    Run run = new Run();
                    run.clueLen = clueStr.length();
                    if (run.clueLen < 1 || run.clueLen > 2)
                        continue;
                    run.clueLetters[0] = letterId(clueStr.charAt(0));
                    run.clueLetters[1] = run.clueLen == 2 ? letterId(clueStr.charAt(1)) : -1;
                    if (run.clueLetters[0] < 0 || (run.clueLen == 2 && run.clueLetters[1] < 0))
                        continue;

                    if (horiz) {
                        for (int cc = c + 1; cc < n; cc++) {
                            int idx = puzzle.whiteIndex[r * n + cc];
                            if (idx < 0)
                                break;
                            run.cells.add(idx);
                        }
                    } else {
                        for (int rr = r + 1; rr < n; rr++) {
                            int idx = puzzle.whiteIndex[rr * n + c];
                            if (idx < 0)
                                break;
                            run.cells.add(idx);
                        }
                    }
                    if (!run.cells.isEmpty())
                        puzzle.runs.add(run);
                }
            }
        }
        return puzzle;
    }

    static List<Puzzle> loadPuzzles(String filepath) {
        List<Puzzle> puzzles = new ArrayList<>();
        try (BufferedReader br = new BufferedReader(new FileReader(filepath))) {
            String line;
            while ((line = br.readLine()) != null) {
                line = line.trim();
                if (line.isEmpty())
                    continue;
                Puzzle p = parsePuzzleLine(line);
                if (p != null)
                    puzzles.add(p);
            }
        } catch (Exception e) {
            // Error handling ignored to fallback
        }
        return puzzles;
    }

    static class PropResult {
        boolean ok, changed;

        PropResult(boolean o, boolean c) {
            ok = o;
            changed = c;
        }
    }

    static PropResult propagateLinks(Puzzle puzzle, State st) {
        boolean changed = false;
        int sz = puzzle.cellLetter.size();
        for (int i = 0; i < sz; i++) {
            int letter = puzzle.cellLetter.get(i);
            if (letter < 0)
                continue;
            int allowed = st.letterDom[letter] & CELL_MASK;
            int cdom = st.cellDom[i];
            int ndom = cdom & allowed;
            if (ndom == 0)
                return new PropResult(false, changed);
            if (ndom != cdom) {
                st.cellDom[i] = ndom;
                changed = true;
            }

            int ldom = st.letterDom[letter];
            int nldom = ldom & ndom;
            if (nldom == 0)
                return new PropResult(false, changed);
            if (nldom != ldom) {
                st.letterDom[letter] = nldom;
                changed = true;
            }
        }
        return new PropResult(true, changed);
    }

    static PropResult propagateAllDiffLetters(State st) {
        boolean changed = false;
        boolean localChanged = true;
        while (localChanged) {
            localChanged = false;
            for (int i = 0; i < LETTERS; i++) {
                if (st.letterDom[i] == 0)
                    return new PropResult(false, changed);
            }

            int assignedMask = 0;
            for (int i = 0; i < LETTERS; i++) {
                if (isSingle(st.letterDom[i]))
                    assignedMask |= st.letterDom[i];
            }

            for (int i = 0; i < LETTERS; i++) {
                if (isSingle(st.letterDom[i]))
                    continue;
                int ndom = st.letterDom[i] & ~assignedMask;
                if (ndom == 0)
                    return new PropResult(false, changed);
                if (ndom != st.letterDom[i]) {
                    st.letterDom[i] = ndom;
                    localChanged = true;
                    changed = true;
                }
            }

            for (int d = 0; d <= 9; d++) {
                int bit = 1 << d;
                int count = 0;
                int where = -1;
                for (int i = 0; i < LETTERS; i++) {
                    if ((st.letterDom[i] & bit) != 0) {
                        count++;
                        where = i;
                    }
                }
                if (count == 0)
                    return new PropResult(false, changed);
                if (count == 1 && st.letterDom[where] != bit) {
                    st.letterDom[where] = bit;
                    localChanged = true;
                    changed = true;
                }
            }
        }
        return new PropResult(true, changed);
    }

    static PropResult propagateRun(Run run, State st) {
        boolean changed = false;
        int len = run.cells.size();
        if (len <= 0 || len > MAX_LEN)
            return new PropResult(false, changed);

        int a = run.clueLetters[0];
        int b = run.clueLetters[1];

        if (run.clueLen == 2) {
            int domA = st.letterDom[a];
            int ndomA = domA & ~1;
            if (ndomA == 0)
                return new PropResult(false, changed);
            if (ndomA != domA) {
                st.letterDom[a] = ndomA;
                changed = true;
            }
        }

        boolean[] sumAllowed = new boolean[MAX_SUM + 1];
        if (run.clueLen == 1) {
            int dom = st.letterDom[a];
            for (int d = 0; d <= 9; d++) {
                if (((dom >> d) & 1) != 0)
                    sumAllowed[d] = true;
            }
        } else {
            int domA = st.letterDom[a];
            int domB = st.letterDom[b];
            for (int da = 0; da <= 9; da++) {
                if (((domA >> da) & 1) == 0)
                    continue;
                for (int db = 0; db <= 9; db++) {
                    if (((domB >> db) & 1) == 0)
                        continue;
                    int s = 10 * da + db;
                    if (s <= MAX_SUM)
                        sumAllowed[s] = true;
                }
            }
        }

        int[] unionMasks = new int[MAX_LEN];
        boolean[] sumValid = new boolean[MAX_SUM + 1];
        boolean anyTuple = false;

        for (int s = 0; s <= MAX_SUM; s++) {
            if (!sumAllowed[s])
                continue;
            List<Long> tuples = tupleCodes[len][s];
            if (tuples.isEmpty())
                continue;
            boolean anyForSum = false;

            for (long code : tuples) {
                boolean ok = true;
                for (int pos = 0; pos < len; pos++) {
                    int d = (int) ((code >> (4 * pos)) & 0xF);
                    int bit = 1 << d;
                    if ((st.cellDom[run.cells.get(pos)] & bit) == 0) {
                        ok = false;
                        break;
                    }
                }
                if (!ok)
                    continue;
                anyForSum = true;
                anyTuple = true;
                for (int pos = 0; pos < len; pos++) {
                    int d = (int) ((code >> (4 * pos)) & 0xF);
                    unionMasks[pos] |= (1 << d);
                }
            }
            if (anyForSum)
                sumValid[s] = true;
        }

        if (!anyTuple)
            return new PropResult(false, changed);

        for (int pos = 0; pos < len; pos++) {
            int cid = run.cells.get(pos);
            int ndom = st.cellDom[cid] & unionMasks[pos];
            if (ndom == 0)
                return new PropResult(false, changed);
            if (ndom != st.cellDom[cid]) {
                st.cellDom[cid] = ndom;
                changed = true;
            }
        }

        if (run.clueLen == 1) {
            int allowed = 0;
            for (int s = 0; s <= 9; s++) {
                if (sumValid[s])
                    allowed |= (1 << s);
            }
            int ndom = st.letterDom[a] & allowed;
            if (ndom == 0)
                return new PropResult(false, changed);
            if (ndom != st.letterDom[a]) {
                st.letterDom[a] = ndom;
                changed = true;
            }
        } else if (a == b) {
            int allowed = 0;
            for (int d = 0; d <= 9; d++) {
                int s = 11 * d;
                if (s <= MAX_SUM && sumValid[s])
                    allowed |= (1 << d);
            }
            allowed &= ~1;
            int ndom = st.letterDom[a] & allowed;
            if (ndom == 0)
                return new PropResult(false, changed);
            if (ndom != st.letterDom[a]) {
                st.letterDom[a] = ndom;
                changed = true;
            }
        } else {
            int allowedA = 0, allowedB = 0;
            int domA = st.letterDom[a], domB = st.letterDom[b];
            for (int da = 0; da <= 9; da++) {
                if (((domA >> da) & 1) == 0)
                    continue;
                for (int db = 0; db <= 9; db++) {
                    if (((domB >> db) & 1) == 0)
                        continue;
                    int s = 10 * da + db;
                    if (s <= MAX_SUM && sumValid[s]) {
                        allowedA |= (1 << da);
                        allowedB |= (1 << db);
                    }
                }
            }
            allowedA &= ~1;
            int ndomA = st.letterDom[a] & allowedA;
            int ndomB = st.letterDom[b] & allowedB;
            if (ndomA == 0 || ndomB == 0)
                return new PropResult(false, changed);
            if (ndomA != st.letterDom[a]) {
                st.letterDom[a] = ndomA;
                changed = true;
            }
            if (ndomB != st.letterDom[b]) {
                st.letterDom[b] = ndomB;
                changed = true;
            }
        }
        return new PropResult(true, changed);
    }

    static boolean propagate(Puzzle puzzle, State st) {
        while (true) {
            boolean globallyChanged = false;

            PropResult r1 = propagateLinks(puzzle, st);
            if (!r1.ok)
                return false;
            if (r1.changed)
                globallyChanged = true;

            PropResult r2 = propagateAllDiffLetters(st);
            if (!r2.ok)
                return false;
            if (r2.changed)
                globallyChanged = true;

            PropResult r3 = propagateLinks(puzzle, st);
            if (!r3.ok)
                return false;
            if (r3.changed)
                globallyChanged = true;

            for (Run run : puzzle.runs) {
                PropResult r4 = propagateRun(run, st);
                if (!r4.ok)
                    return false;
                if (r4.changed)
                    globallyChanged = true;
            }

            if (!globallyChanged)
                break;
        }
        return true;
    }

    static boolean solved(State st) {
        for (int i = 0; i < LETTERS; i++) {
            if (!isSingle(st.letterDom[i]))
                return false;
        }
        for (int dom : st.cellDom) {
            if (!isSingle(dom))
                return false;
        }
        return true;
    }

    static class Choice {
        boolean isLetter = true;
        int idx = -1;
        int dom = 0;
        int size = 1000;
    }

    static Choice chooseVariable(State st) {
        Choice best = new Choice();
        for (int i = 0; i < LETTERS; i++) {
            int sz = popcount(st.letterDom[i]);
            if (sz > 1 && sz < best.size) {
                best.isLetter = true;
                best.idx = i;
                best.dom = st.letterDom[i];
                best.size = sz;
            }
        }
        for (int i = 0; i < st.cellDom.length; i++) {
            int sz = popcount(st.cellDom[i]);
            if (sz > 1 && sz < best.size) {
                best.isLetter = false;
                best.idx = i;
                best.dom = st.cellDom[i];
                best.size = sz;
            }
        }
        return best;
    }

    static boolean dfsSolve(Puzzle puzzle, State st) {
        if (!propagate(puzzle, st))
            return false;
        if (solved(st))
            return true;

        Choice choice = chooseVariable(st);
        if (choice.idx < 0)
            return false;

        for (int d = 0; d <= 9; d++) {
            int bit = 1 << d;
            if ((choice.dom & bit) == 0)
                continue;

            State next = st.copy();
            if (choice.isLetter)
                next.letterDom[choice.idx] = bit;
            else
                next.cellDom[choice.idx] = bit;

            if (dfsSolve(puzzle, next)) {
                System.arraycopy(next.letterDom, 0, st.letterDom, 0, LETTERS);
                System.arraycopy(next.cellDom, 0, st.cellDom, 0, st.cellDom.length);
                return true;
            }
        }
        return false;
    }

    static long solvePuzzle(Puzzle puzzle) {
        State st = new State(puzzle.cellLetter.size());
        if (!dfsSolve(puzzle, st))
            return -1;

        long encryptedValue = 0;
        for (int i = 0; i < LETTERS; i++) {
            encryptedValue = encryptedValue * 10 + singleValue(st.letterDom[i]);
        }
        return encryptedValue;
    }

    static String solve() {
        prepareTuples();
        String file = "p424_kakuro200.txt";
        List<Puzzle> puzzles = loadPuzzles(file);
        if (puzzles.isEmpty()) {
            file = "solutionsCpp/p424_kakuro200.txt";
            puzzles = loadPuzzles(file);
        }

        long total = 0;
        for (Puzzle p : puzzles) {
            long val = solvePuzzle(p);
            if (val >= 0)
                total += val;
        }
        return Long.toString(total);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}