M2. Mondridalgo (Optimization)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The motivating story and definition of a rectilinear path (and related terms) are the same in Mondridalgo (Verification) and (Optimization). Skip to the bolded text for the first section where the two differ.

Bob created a magnificent painting this year in the Mondridalgo style (a combination of Piet Mondrian's rectangles and Felix Hidalgo's neoclassicism), which both Alice and Cindy adore. Unfortunately, when Cindy asked him if she could keep the painting, he was too lovestruck and immediately said yes... forgetting that he had already previously promised the painting to Alice! Oh no! Remember everyone—don't be like Bob.

Unable to choose between his two friends, Bob decides the best way to resolve this situation is to cut up his painting into two contiguous pieces using a pair of scissors, and then hand one piece to Alice and the other Cindy. That way, each of his friends is equally unhappy.

We formalize "cutting with scissors" by defining a rectilinear path to be a non-empty sequence of "cuts" such that:

  • Each cut is represented by a directed line segment, indicating the motion of cutting.
  • The first cut starts somewhere along the border of the painting, and moves perpendicular to the border.
  • Each next cut in the sequence begins where the previous one ended, and is oriented perpendicular to the previous cut.
  • The final cut should end anywhere along the border.
A valid rectilinear path is one that partitions the painting into exactly two regions (one to hand to Alice and one to hand to Cindy). We can show that the following conditions make a rectilinear path valid:
  • All cuts are made along the gridlines, and with the exception of the start of the first cut and the end of the last cut, the path must stay entirely within the rectangle at all times.
  • Any two non-consecutive cuts should not intersect anywhere, not even at a point.
See the Notes below for illustrations of rectilinear cuts. Each one splits the painting into two regions, colored blue and red in the diagrams. They use $$$1$$$, $$$2$$$, and $$$4$$$ cuts, respectively.
For the optimization problem, Alice assigned a integer "Alice adoration rating" to each square in the painting, indicating her happiness if she receives this square of the painting; Cindy similarly assigned an integer "Cindy cherish rating" to each square in the painting. These ratings can also be negative, indicating squares that they really do not like. Alice's happiness is equal to the sum of the Alice adoration ratings of all squares given to her; Cindy's happiness is equal to the Cindy cherish ratings of all squares given to her.

Our goal is to try to find a partition which is not "lop-sided"—that is, neither one of Alice nor Cindy should be significantly happier than the other in this interaction. This partition also shouldn't be too complicated.

Formally, given an integer $$$k$$$, find any partition whose valid rectilinear path uses at least $$$1$$$ and at most $$$k$$$ cuts, and which minimizes the value $$$|\text{Alice's happiness} - \text{Cindy's happiness}|$$$ among such partitions.

Input

The first line of input contains the three space-separated integers $$$r$$$ and $$$c$$$ and $$$k$$$.

Then, an $$$r \times c$$$ grid follows, describing the Alice adoration ratings—that is, $$$r$$$ lines follow, each containing $$$c$$$ integers: $$$$$$ \begin{array}{cccc} u_{1, 1} & u_{1, 2} & \dots & u_{1, c} \\ u_{2, 1} & u_{2, 2} & \dots & u_{2, c} \\ \vdots & \vdots & \ddots & \vdots \\ u_{r, 1} & u_{r, 2} & \dots & u_{r, c} \end{array} $$$$$$ where $$$u_{i, j}$$$ is the Alice adoration rating of the square in the $$$i$$$th row from the top and $$$j$$$th column from the left.

Then, another $$$r \times c$$$ grid follows, describing the Cindy cherish ratings—that is, $$$r$$$ lines follow, each containing $$$c$$$ integers: $$$$$$ \begin{array}{cccc} v_{1, 1} & v_{1, 2} & \dots & v_{1, c} \\ v_{2, 1} & v_{2, 2} & \dots & v_{2, c} \\ \vdots & \vdots & \ddots & \vdots \\ v_{r, 1} & v_{r, 2} & \dots & v_{r, c} \end{array} $$$$$$ where $$$v_{i, j}$$$ is the Cindy cherish rating of the square in the $$$i$$$th row from the top and $$$j$$$th column from the left.

Output

Output a single positive integer—the minimal value of $$$|\text{Alice's happiness} - \text{Cindy's happiness}|$$$.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq r, c \leq 6 \\ 1 \leq k \leq 6 \\ \text{$-10^9 \leq u_{i, j}, v_{i, j} \leq 10^9$ for each $i, j$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & k=1 \\ \hline 2 & \mathbf{30} & k \leq 2 \\ \hline 3 & \mathbf{20} & r, c \leq 3 \\ \hline 4 & \mathbf{20} & r, c \leq 4 \\ \hline 5 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
4 5 1
20 -8 11 4 0
-7 -5 12 9 -2
12 12 -9 5 -2
11 10 12 1 -2
-9 -6 -9 -2 9
15 22 -5 -6 9
-1 21 -5 10 9
-1 29 -5 10 9
Output
10
Input
4 5 2
20 -8 11 4 0
-7 -5 12 9 -2
12 12 -9 5 -2
11 10 12 1 -2
-9 -6 -9 -2 9
15 22 -5 -6 9
-1 21 -5 10 9
-1 29 -5 10 9
Output
1
Input
4 5 5
20 -8 11 4 0
-7 -5 12 9 -2
12 12 -9 5 -2
11 10 12 1 -2
-9 -6 -9 -2 9
15 22 -5 -6 9
-1 21 -5 10 9
-1 29 -5 10 9
Output
0
Input
4 5 6
20 -8 11 4 0
-7 -5 12 9 -2
12 12 -9 5 -2
11 10 12 1 -2
-9 -6 -9 -2 9
15 22 -5 -6 9
-1 21 -5 10 9
-1 29 -5 10 9
Output
0
Note

Here are the corresponding partitions for the first three sample inputs.

For example, in the first sample input, Alice's happiness would be $$$20 + (-8) + 11 + 4 + 0 + (-7) + (-5) + 12 + 9 + (-2) + 11 + 10 + 12 + 1 + (-2) = 52$$$. Meanwhile, Cindy's happiness is $$$(-1) + 29 + (-5) + 10 + 9 = 42$$$. We can show that the difference of $$$|52 - 42| = 10$$$ is minimal across all partitions that use one cut.