Problem 345: Matrix Sum

Project Euler Problem 345 Solution

EulerSolve provides an optimized solution for Project Euler Problem 345, Matrix Sum, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We are given an $n\times n$ matrix and must choose exactly one entry from each row and exactly one from each column so that the total sum is as large as possible. This is the maximum-weight assignment problem, or equivalently a maximum-weight perfect matching in a complete bipartite graph. Mathematical Approach Let $A=(A_{r,c})_{0\le r,c\lt n}$ be the matrix. Any valid selection is completely determined by a permutation $\pi\in S_n$: row $r$ is matched with column $\pi(r)$. Therefore the target quantity is $$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$ Why Brute Force Is Too Expensive A direct search would test all $n!$ permutations. For $n=15$, this means $$15! = 1{,}307{,}674{,}368{,}000,$$ which is far too large for exhaustive enumeration. The only practical route is to reuse overlapping subproblems, which is exactly what dynamic programming does. Bitmask DP State The key observation is that after assigning the first $r$ rows, the only information that matters is which columns have already been used. We encode this set by a bitmask $\text{mask}\in[0,2^n)$, where bit $c$ is 1 iff column $c$ has been taken....

Detailed mathematical approach

Problem Summary

The Matrix Sum of a square matrix is the largest total reachable by selecting elements so that no two share a row or a column. The statement illustrates it with a $5\times5$ matrix whose Matrix Sum is $3315=863+383+343+959+767$, then asks for that of a $15\times15$ matrix of positive integers ranging from $3$ to $993$. ^[1]

The whole solution in one sentence: a best selection takes exactly one element from every row and every column, so we fill the rows one at a time and remember nothing but which columns are already used, which replaces the $15!$ orderings by the $2^{15}$ subsets of columns.

Mathematical Approach

1. What a legal selection looks like

Write $A_{r,c}$ for the entry in row $r$ and column $c$, rows and columns numbered $0,1,\dots,n-1$. A legal selection is a set of cells with at most one per row and one per column. The statement does not say how many to choose, but the count is forced: every entry is positive, the smallest being $3$, so if fewer than $n$ were used, some row $r$ and some column $c$ would both be untouched and adding $(r,c)$ would raise the total. An optimal selection has exactly $n$ cells, one per row and one per column — a permutation $\pi$ of the columns, row $r$ contributing $A_{r,\pi(r)}$. So the Matrix Sum is

$$\max_{\pi\in S_n}\ \sum_{r=0}^{n-1}A_{r,\pi(r)},$$

with $S_n$ the set of all $n!$ permutations. Reading rows and columns as the two sides of a bipartite graph and $A_{r,c}$ as an edge weight, this is the classical assignment problem: a maximum-weight perfect matching. ^[2]

2. Why enumerating permutations fails

The obvious program tries every permutation. For $n=15$ that is

$$15!=1\,307\,674\,368\,000$$

candidates, over twenty minutes even at an optimistic billion per second. Most of that work repeats: all permutations giving rows $0,1,2$ the columns $\{1,4,7\}$, in any of the six ways, face the same remaining task. Exploiting that repetition is the whole idea.

3. Only the set of used columns matters

Fix the order in which the rows are served — row $0$ first, then row $1$, and so on — which loses nothing, since a selection is a set and may be built in any order. Suppose rows $0,\dots,r-1$ have already received columns. The remaining rows need only the set $S$ of columns taken: which row took which inside $S$ cannot change what is still allowed, and the objective is a plain sum, so the two groups interact through $S$ alone. Better still, the number of rows served is $|S|$, each having taken one column, so the set describes the state completely. In a program $S$ becomes a bitmask, an integer in $[0,2^n)$ whose bit $c$ is $1$ exactly when column $c$ is taken. For $n=3$ the set $\{0,2\}$ is the mask $101_2=5$, whose two set bits say that rows $0$ and $1$ are served and row $2$ is next.

This is subset dynamic programming. The travelling-salesman algorithms found independently in 1962 by Bellman and by Held and Karp use the same idea but must also remember the current endpoint, giving $\Theta(n\,2^n)$ states; the fixed row order spares us that coordinate. ^[4]

4. The recurrence over column subsets

For a set $S\subseteq\{0,\dots,n-1\}$ of columns put $r=|S|$ and define

$$D(S)=\max_{\sigma}\ \sum_{j=0}^{r-1}A_{j,\sigma(j)},$$

the maximum over all $r!$ bijections $\sigma$ from $\{0,\dots,r-1\}$ onto $S$: the best total rows $0$ to $r-1$ can reach on exactly the columns of $S$. So $D$ is defined on every subset, $D(\emptyset)=0$, and we want $D(\{0,\dots,n-1\})$. Asking which column the last served row took gives, for $r\ge1$,

$$D(S)=\max_{c\in S}\bigl(D(S\setminus\{c\})+A_{r-1,c}\bigr).$$

The published programs run this forwards: from $S$ with $|S|=r\lt n$ and any column $c\notin S$ they offer $D(S)+A_{r,c}$ as a candidate for $S\cup\{c\}$. The backward form scans the $|S|$ elements of each subset, the forward form the $n-|S|$ columns outside it; Section 7 shows the totals agree.

5. Why the recurrence is correct

We prove the equality; induction on $|S|$ then determines $D$ everywhere, since every set on the right is smaller.

Left at most right. Let $\sigma$ attain $D(S)$ and $c=\sigma(r-1)$ be the column of the last served row. Deleting that pair leaves a bijection onto $S\setminus\{c\}$, of value at most $D(S\setminus\{c\})$, so $D(S)\le D(S\setminus\{c\})+A_{r-1,c}$ — one of the terms being maximised.

Right at most left. Pick any $c\in S$ and a bijection $\tau$ onto $S\setminus\{c\}$ attaining $D(S\setminus\{c\})$. Sending row $r-1$ to $c$ extends $\tau$ to a bijection onto $S$ of value $D(S\setminus\{c\})+A_{r-1,c}$, so $D(S)$ is at least that; maximise over $c$.

Two things follow. Every subset is reachable, since $D(S)$ maximises over a non-empty set of bijections; and the row order was arbitrary, since Section 1 identified the final value with a maximum over permutations.

6. A worked example by hand

Take the top-left $3\times3$ corner of the $5\times5$ example, rows $(7,53,183)$, $(497,383,563)$ and $(287,63,343)$. Its six permutations give $903$, $893$, $853$, $743$, $733$ and $633$, so the Matrix Sum is $903=53+563+287$. Now the recurrence, one subset size at a time:

$D(\emptyset)=0$.
One column, served by row $0$: $D(\{0\})=7$, $D(\{1\})=53$ and $D(\{2\})=183$.
Two columns, row $1$ last. For $S=\{0,1\}$ the candidates are $7+383$ and $53+497$, so $D(\{0,1\})=550$; likewise $D(\{0,2\})=680$ from $7+563$ and $183+497$, and $D(\{1,2\})=616$ from $53+563$ and $183+383$.
Three columns, row $2$ last: the candidates $550+343$, $680+63$ and $616+287$ give $D(\{0,1,2\})=903$.

The two methods agree, and both spent $12$ additions: nothing is saved at $n=3$. The gap opens with $n$, reaching $245\,760$ against $15!\cdot14$, over $1.8\cdot10^{13}$. Note too that the winning route passes through $D(\{1,2\})=616$, not the best two-column value: no single partial state may be followed greedily.

7. Exactly how many steps it takes

Each subset $S$ with $|S|=r\lt n$ offers $n-r$ free columns, and each costs one addition and one comparison. Summing over subsets,

$$\begin{aligned}\sum_{r=0}^{n-1}\binom{n}{r}(n-r)&=\sum_{k=1}^{n}k\binom{n}{k}\\&=n\,2^{n-1},\end{aligned}$$

where the middle step substitutes $k=n-r$ and uses $\binom{n}{n-k}=\binom{n}{k}$. The closed form counts pairs $(c,S)$ with $c\in S$: each column lies in $2^{n-1}$ subsets. The same total comes out of $\sum_S|S|$, which is why the backward form costs the same. This is OEIS A001787, also the number of edges of the $n$-dimensional cube ^[6] — fitting, since our states are that cube's vertices and each step moves along an edge. For $n=3$ it gives the twelve additions of Section 6, for $n=5$ it gives $80$, and for $n=15$,

$$15\cdot2^{14}=245\,760.$$

8. Greedy choices do not work

It is tempting to grab the largest entry, cross out its row and column, and repeat. The smallest counterexample is the $2\times2$ matrix with rows $(10,9)$ and $(9,1)$: taking $10$ leaves only $1$, total $11$, while the other selection gives $9+9=18$. It fails on the $5\times5$ example too, where taking the largest available entry repeatedly picks $973$, $959$, $767$, $343$, $53$, total $3095$, short of $3315$ by $220$; going row by row from the top picks $863$, $563$, $287$, $959$, $473$, total $3145$, also short.

9. A certificate of optimality, and the polynomial alternative

The recurrence produces a number, but can we check that nothing beats it without trusting a program? Give each row $r$ a number $u_r$ and each column $c$ a number $v_c$ with

$$u_r+v_c\ \ge\ A_{r,c}$$

for every row $r$ and every column $c$. Then for any permutation $\pi$,

$$\begin{aligned}\sum_r A_{r,\pi(r)}&\le\sum_r\bigl(u_r+v_{\pi(r)}\bigr)\\&=\sum_r u_r+\sum_c v_c,\end{aligned}$$

because $\pi$ uses every column once. Any such pair of lists therefore bounds the Matrix Sum by its own total: weak duality for the linear program behind the assignment problem. ^[5] For the $5\times5$ example take

$$\begin{aligned}u&=(273,383,160,590,473),\\v&=(294,0,183,369,590).\end{aligned}$$

All $25$ inequalities hold and the totals are $1879$ and $1436$, so nothing can exceed $3315$; the selection in the statement reaches it, so $3315$ is exactly the Matrix Sum. Given the two lists the check is twenty-five sums against twenty-five entries plus the totals, and no search. The bound is tight at the five chosen cells $(0,4)$, $(1,1)$, $(2,2)$, $(3,3)$ and $(4,0)$, and tightness along a full selection is what forces equality.

Such numbers are potentials, and the Hungarian method builds them as it runs. Its textbook form minimises a cost, with potentials satisfying $y(i)+y(j)\le c(i,j)$; to use it here, negate the matrix. With $B_{r,c}=-A_{r,c}$, minimising the selected entries of $B$ maximises those of $A$, and $-u_r$, $-v_c$ satisfy that reversed inequality. Published by Kuhn in 1955 and named after earlier results of Kőnig and Egerváry, the method runs in $O(n^3)$ after refinements of the original $O(n^4)$. ^[3] That growth beats $n\,2^{n-1}$ decisively, so for large $n$ it is the only option: at $n=100$ the subset recurrence would need $2^{100}$ stored values. At $n=15$ both finish at once and the recurrence wins only on brevity.

How the Code Works

All three programs evaluate Section 4 bottom-up over column masks, packaged differently: C++ holds the recurrence in matrix_sum and Java in matrixSum, each taking a matrix, with solve supplying the $15\times15$ literal, while Python has only solve, literal and loop together. C++ returns an integer from solve, Java and Python a string.

In C++, matrix_sum reads $n$ from the matrix's size, sets full to $2^n$, allocates std::vector<i64> dp(full, -1) and writes dp[0] = 0, the $-1$ marking an entry not yet filled. The sweep runs over mask from $0$ to full - 1 in plain numerical order, and that is what makes the forward form work: adding a column sets a bit, so mask | (1 << col) exceeds mask. Numerical order is a topological order of the subset lattice, so no recursion or sorting by size is needed.

Inside the sweep base = dp[mask] reads the current value, and base < 0 skips an unfilled state. That guard comes first, before anything else is computed, and for a square matrix never fires, since every subset is reachable by Section 5. Only then does __builtin_popcount(mask) count the set bits to recover $r=|S|$ ^[7]; how many machine instructions that takes depends on compiler and target. The second guard, row >= n, skips the full mask alone and is a pure shortcut, since without it every column of that mask would fail the used-column test (mask & (1 << col)) != 0 before a[row] was reached. Otherwise the inner loop relaxes the successor with std::max, and the result is dp[full - 1], that is $D(\{0,\dots,n-1\})$.

Only the C++ program checks itself: run_checkpoints runs matrix_sum on the $5\times5$ matrix and insists on $3315$, exiting with code $2$ on failure, while parse_arguments accepts --skip-checkpoints and rejects anything else with code $1$. ^[8] The ports have no self-test and differ only in detail: Java needs Arrays.fill(dp, -1), since the virtual machine zero-fills a new long[], and counts bits with Integer.bitCount(mask); Python uses dp = [-1] * full and bin(mask).count('1'), documented as the equivalent of int.bit_count(). ^[7] Integer width is generous: no total exceeds $15\cdot993=14\,895$, yet C++ uses long long and Java long. Both keep masks in an int, so 1 << n breaks above thirty rows — moot, since $2^{30}$ eight-byte entries already need $8$ GiB.

A last caveat belongs to the $-1$ marker rather than the mathematics. It is safe for non-negative entries, since no stored value can then be mistaken for it, but negative entries break the loop twice over. The marker is ambiguous: rows $(-4,0)$ and $(-8,-18)$ yield $-1$ where the best one-per-row-and-column selection totals $-8$. Worse, base < 0 throws away genuinely negative partial totals, so rows $(-1,-2)$ and $(5,4)$ miss the optimum $3$ however negative the marker is made. A repair needs both a marker below every attainable total and a guard testing for that marker, not for a negative sign. Negative entries also break Section 1, whose rule allows fewer cells: the first example's Matrix Sum is $0$, from its single zero entry.

Complexity and Verification

Counting integer operations at unit cost, the time is $\Theta(n\,2^{n})$. For $n=15$ the outer loop does $2^{15}=32\,768$ population counts and the inner loop tests every column of every non-full mask: $n(2^n-1)=491\,505$ tests, of which the $n\,2^{n-1}=245\,760$ relaxations of Section 7 survive, each an addition, a comparison and at most a store. Python also builds and scans a binary string per count, $O(n)$ a mask, inside the same bound.

Storage is $\Theta(2^{n})$ values: at $n=15$ the $32\,768$ entries of Java's long[] occupy $256$ KiB, as does the C++ vector where long long is eight bytes, excluding container overhead and the matrix. Python keeps references to integer objects, so its footprint is not eight bytes a value. Either way this is a factor $n$ below the $\Theta(n\,2^{n})$ travelling-salesman table, which stores an endpoint too. ^[4]

Beyond the packaged checkpoint, these checks were run for this article and are not part of the programs.

All $120$ permutations of the $5\times5$ example confirm $3315$, attained only by the selection highlighted in the statement: columns $4,1,2,3,0$ for rows $0,\dots,4$.
For the leading $k\times k$ submatrices of the $15\times15$ matrix it agrees with brute force over all $k!$ permutations when $k\le9$ — $7$, $680$, $1273$, $2282$, $3868$, $4578$, $5712$, $7114$, $7818$ — and with an independent Hungarian implementation for $10\le k\le14$. Beware that $3868$, not $3315$, is the leading $5\times5$ value: the statement's example is the first twenty-five numbers of the large matrix read row by row, five to a line, not its top-left corner.
From one generator seeded with $345$, $400$ matrices of size up to $9$ and $300$ of size up to $8$ were filled with entries drawn uniformly from $0$ to $999$, so all non-negative; the recurrence matched the Hungarian implementation on the first batch and exhaustive search on the second, every time.
The instrumented loop makes exactly $n(2^n-1)$ column tests and $n\,2^{n-1}$ relaxations, as Section 7 predicts; base < 0 never skips a mask and row >= n skips only the full one.
The best four-cell selection in the $5\times5$ example totals $3152$, below $3315$, as Section 1 predicts; the potentials of Section 9 satisfy all $25$ inequalities and total $3315$; the three programs agree.

Footnotes and References

The references supply the background facts; the reduction to column subsets, the proof of the recurrence, the step count and the optimality certificate are derived here.

Project Euler 345 — Matrix Sum. The official statement defines the Matrix Sum as the maximum possible sum of matrix elements such that none share a row or column, gives 3315 = 863 + 383 + 343 + 959 + 767 for its 5×5 example and asks for that of a 15×15 matrix.
Wikipedia — Assignment problem. It states the problem as a bijection between two equal-sized sets optimising a sum of weights, equivalently a perfect matching of extremal weight in a bipartite graph, notes the n! naive assignments, and gives the linear program underlying Section 9.
Wikipedia — Hungarian algorithm. It credits Harold Kuhn (1955), who named the method after earlier work of Dénes Kőnig and Jenő Egerváry, records the improvement of O(n⁴) to O(n³) by Edmonds and Karp and independently Tomizawa, and defines a potential by y(i) + y(j) ≤ c(i, j), every perfect matching costing at least its value.
Wikipedia — Held–Karp algorithm. It describes dynamic programming over subsets, proposed independently in 1962 by Bellman and by Held and Karp, with Θ(2ⁿn²) time and Θ(n·2ⁿ) space against the Θ(n!) of brute force — contrasted in Section 3 with the Θ(2ⁿ) states here.
Wikipedia — Dual linear program. For the pair "maximise cᵀx, Ax ≤ b, x ≥ 0" and "minimise bᵀy, Aᵀy ≥ c, y ≥ 0" it states weak duality: every feasible dual value bounds the primal optimum above, the argument of Section 9.
OEIS A001787 — n·2^(n−1). The entry gives a(n) = n·2^(n−1), the identity a(n) = Sum_{k=1..n} k·binomial(n, k) and the reading as the edge count of an n-dimensional hypercube, both used in Section 7.
GCC manual — Bit Operation Builtins documents __builtin_popcount as returning the number of 1-bits in x, and Java — Integer.bitCount the one-bits of an int, the population count. Python — numeric types documents int.bit_count() (Python 3.10) with bin(self).count("1") as its equivalent, the spelling the solution uses, and gives Python integers unlimited precision.
C++ — Euler345.cpp. The linked immutable revision contains matrix_sum, solve, parse_arguments and the run_checkpoints comparison against 3315, and is the implementation record here.

Problem 345 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    bool run_checkpoints = true;
};

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

i64 matrix_sum(const std::vector<std::vector<int>>& a) {
    const int n = static_cast<int>(a.size());
    const int full = 1 << n;
    std::vector<i64> dp(static_cast<std::size_t>(full), -1);
    dp[0] = 0;

    for (int mask = 0; mask < full; ++mask) {
        const i64 base = dp[static_cast<std::size_t>(mask)];
        if (base < 0) {
            continue;
        }
        const int row = __builtin_popcount(static_cast<unsigned>(mask));
        if (row >= n) {
            continue;
        }
        for (int col = 0; col < n; ++col) {
            if ((mask & (1 << col)) != 0) {
                continue;
            }
            const int next = mask | (1 << col);
            dp[static_cast<std::size_t>(next)] =
                std::max(dp[static_cast<std::size_t>(next)],
                         base + static_cast<i64>(a[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)]));
        }
    }
    return dp[static_cast<std::size_t>(full - 1)];
}

i64 solve() {
    const std::vector<std::vector<int>> m = {
        {7,53,183,439,863,497,383,563,79,973,287,63,343,169,583},
        {627,343,773,959,943,767,473,103,699,303,957,703,583,639,913},
        {447,283,463,29,23,487,463,993,119,883,327,493,423,159,743},
        {217,623,3,399,853,407,103,983,89,463,290,516,212,462,350},
        {960,376,682,962,300,780,486,502,912,800,250,346,172,812,350},
        {870,456,192,162,593,473,915,45,989,873,823,965,425,329,803},
        {973,965,905,919,133,673,665,235,509,613,673,815,165,992,326},
        {322,148,972,962,286,255,941,541,265,323,925,281,601,95,973},
        {445,721,11,525,473,65,511,164,138,672,18,428,154,448,848},
        {414,456,310,312,798,104,566,520,302,248,694,976,430,392,198},
        {184,829,373,181,631,101,969,613,840,740,778,458,284,760,390},
        {821,461,843,513,17,901,711,993,293,157,274,94,192,156,574},
        {34,124,4,878,450,476,712,914,838,669,875,299,823,329,699},
        {815,559,813,459,522,788,168,586,966,232,308,833,251,631,107},
        {813,883,451,509,615,77,281,613,459,205,380,274,302,35,805}
    };
    return matrix_sum(m);
}

bool run_checkpoints() {
    const std::vector<std::vector<int>> sample = {
        {7,53,183,439,863},
        {497,383,563,79,973},
        {287,63,343,169,583},
        {627,343,773,959,943},
        {767,473,103,699,303}
    };
    if (matrix_sum(sample) != 3315) {
        std::cerr << "Checkpoint failed for 5x5 sample matrix" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve() << '\n';
    return 0;
}

Python

def solve():
    m = [
        [7,53,183,439,863,497,383,563,79,973,287,63,343,169,583],
        [627,343,773,959,943,767,473,103,699,303,957,703,583,639,913],
        [447,283,463,29,23,487,463,993,119,883,327,493,423,159,743],
        [217,623,3,399,853,407,103,983,89,463,290,516,212,462,350],
        [960,376,682,962,300,780,486,502,912,800,250,346,172,812,350],
        [870,456,192,162,593,473,915,45,989,873,823,965,425,329,803],
        [973,965,905,919,133,673,665,235,509,613,673,815,165,992,326],
        [322,148,972,962,286,255,941,541,265,323,925,281,601,95,973],
        [445,721,11,525,473,65,511,164,138,672,18,428,154,448,848],
        [414,456,310,312,798,104,566,520,302,248,694,976,430,392,198],
        [184,829,373,181,631,101,969,613,840,740,778,458,284,760,390],
        [821,461,843,513,17,901,711,993,293,157,274,94,192,156,574],
        [34,124,4,878,450,476,712,914,838,669,875,299,823,329,699],
        [815,559,813,459,522,788,168,586,966,232,308,833,251,631,107],
        [813,883,451,509,615,77,281,613,459,205,380,274,302,35,805]
    ]
    n = len(m)
    full = 1 << n
    dp = [-1] * full
    dp[0] = 0
    for mask in range(full):
        base = dp[mask]
        if base < 0:
            continue
        row = bin(mask).count('1')
        if row >= n:
            continue
        for col in range(n):
            if mask & (1 << col):
                continue
            nxt = mask | (1 << col)
            val = base + m[row][col]
            if val > dp[nxt]:
                dp[nxt] = val
    return str(dp[full - 1])

if __name__ == '__main__':
    print(solve())

Java

import java.util.Arrays;

public class Euler345 {

    static long matrixSum(int[][] a) {
        int n = a.length;
        int full = 1 << n;
        long[] dp = new long[full];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask < full; mask++) {
            long base = dp[mask];
            if (base < 0)
                continue;

            int row = Integer.bitCount(mask);
            if (row >= n)
                continue;

            for (int col = 0; col < n; col++) {
                if ((mask & (1 << col)) != 0)
                    continue;

                int next = mask | (1 << col);
                dp[next] = Math.max(dp[next], base + a[row][col]);
            }
        }
        return dp[full - 1];
    }

    public static String solve() {
        int[][] m = {
                { 7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583 },
                { 627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913 },
                { 447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743 },
                { 217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350 },
                { 960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350 },
                { 870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803 },
                { 973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326 },
                { 322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973 },
                { 445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848 },
                { 414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198 },
                { 184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390 },
                { 821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574 },
                { 34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699 },
                { 815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107 },
                { 813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805 }
        };
        long ans = matrixSum(m);
        return String.valueOf(ans);
    }

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