EllysGarbage

Elly became a manager of a garbage-recycling facility. One of the jobs of the facility is to compress the left-over garbage. In order to do this it is put in a special rectangular room with length N and width M. Each of the four walls of the room can move and press the garbage from its side. Once pressed, some of the garbage gets "compressed" and we can assume it disappears.

We can represent the room as a rectangular matrix with N rows and M columns. Using the left wall makes the leftmost column disappear and using the right wall makes the rightmost column disappear. Similarly, the upper wall makes the topmost row disappear and the bottom wall makes the bottommost row disappear. The goal is to compress all the garbage, or, in other words, make all the cells of the matrix disappear.

Some of the garbage is harder to compress than other (for example, metal requires much stronger force than paper) and making it disappear requires more energy. We've approximated the "hardness" of a cell of garbage with the numbers from 0 to 9, inclusive. Thus, the room is represented as a matrix with N rows and M columns, where each cell contains a single digit – how much force is required to compress the garbage in that cell.

Compressing a row or column of garbage requires energy, equal to the largest number in that row or column. For example, if we'd like to compress a row with cells {4, 7, 3} we would require 7 units of energy. If, instead, we wanted to compress a row with cells {3, 3, 3, 3, 3, 3}, we would require only 3 units.

Let's take a look at the following example of a room with 3 rows and 4 columns:

1 9 2 4
1 9 0 3
2 7 8 6

If we press the top wall (the row with numbers 1, 9, 2, 4) we would need 9 units of energy, since this is the largest number in that row. Similarly, for the bottom row we would need 8 units, for the left column we would need 2 and for the right one we would need 6. It turns out that it matters which walls we use and in what order. For example, if we only used the top wall we would need 9 + 9 + 8 = 26 units of energy. If, instead, we used the bottom one, the left one, the left one again, the right one and the top one, we would need only 8 + 1 + 9 + 4 + 2 = 24 units.

Elly wants to make the recycling facility as efficient as possible. In order to do this, she wants to compress the garbage using the smallest amount of energy. She wants you to write a program that finds thi minimal amount of energy. You are given the description of the garbage in the String[] garbage. Return a single int - the minimal possible total energy used to compress all of the garbage.