Woburn Challenge 2017-18 Round 4 - Senior Division

With the fate of the entire galaxy on the line, the Guardians of the Galaxy have naturally been called in to battle against Thanos as well! That being said, their leader, Star-Lord, has realized the potential for a bit of financial compensation along the way. He's successfully secured a hefty stash of solid gold coins for his team before any fighting has even begun!

While waiting for the action to finally get underway, Rocket Raccoon and Groot have decided to amuse themselves with a game involving the coins. For starters, they've drawn a grid on the ground with ~N~ rows and ~N~ columns ~(1 \le N \le 1\,000)~. Then, in each cell ~(i, j)~ (the cell in the ~i~-th row and ~j~-th column), they've placed a stack of ~C_{i, j}~ ~(1 \le C_{i, j} \le 10^9)~ coins.

If you look at the resulting coin collection from the South (from beyond row ~1~), all you can make out is the shape of its "skyline". This Southern skyline is a sequence of ~N~ positive integers, the ~i~-th of which is the number of coins in the tallest stack in the ~i~-th column. Similarly, its Western skyline (when viewed from beyond column ~1~) is a sequence of ~N~ positive integers, the ~i~-th of which is the number of coins in the tallest stack in the ~i~-th row.

For example, consider the following arrangement of stack heights:

2 3 2
4 5 4
5 1 2

Its Southern skyline sequence is ~\{5, 5, 4\}~, while its Western skyline sequence is ~\{3, 5, 5\}~.

Rocket Raccoon now poses the following challenge to Groot: Remove ~0~ or more coins from the collection such that it will look exactly the same from the South as from the West (in other words, such that its Southern skyline sequence will be equal to its Western skyline sequence). Groot has a bit of trouble lifting the heavy gold coins, so he'd like to pass Rocket Raccoon's challenge while removing as few of them as possible. What's the minimum number of coins which he must remove from the stacks in total? Note that this value may not fit into a ~32~-bit signed integer.

Subtasks

In test cases worth ~9/28~ of the points, ~N \le 200~ and ~C_{i, j} \le 2~ for each cell ~(i, j)~.
In test cases worth another ~9/28~ of the points, ~N \le 200~.

Input Specification

The first line of input consists of a single integer, ~N~.
~N~ lines follow, the ~i~-th of which consists of integers, ~C_{i,1 \dots N}~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, the minimum number of coins which Groot must remove.

Sample Input

3
2 3 2
4 5 4
5 1 2

Sample Output

4

Sample Explanation

One option is for Groot to remove one coin from the stack in cell ~(2, 1)~, one coin from ~(2, 3)~, and two coins from ~(3, 1)~, resulting in the following arrangement of stack heights:

2 3 2
3 5 3
3 1 2

Note that both its Southern and Western skyline sequences are equal to ~\{3, 5, 3\}~.