Background

Zijin has a game board and is going to take it out to play.

Problem Description

Her board is L-shaped. It consists of an upper small rectangle of size $n_1 \times m_1$ and a lower large rectangle of size $n_2 \times m_2$. Initially, the number in every cell on the board is $k$.

For example, when $n_1 = 2$, $m_1 = 2$, $n_2 = 3$, $m_2 = 4$, $k = 0$, the initial board looks like this:

0 0
0 0
0 0 0 0
0 0 0 0
0 0 0 0

Now she will perform several operations: add $1$ or subtract $1$ to the numbers in two adjacent cells at the same time. After finishing the operations, she will remember the numbers in these cells.

However, she made a mistake once. After several operations, she forgot what one of the numbers was, so she wrote $999999$ there. Please write a program to find what the number marked as $999999$ should be. It is guaranteed that exactly one cell is marked as $999999$.

Input Format

The first line contains five integers $n_1, m_1, n_2, m_2, k$, representing the number of rows and columns of the small rectangle forming the L-shaped board, the number of rows and columns of the large rectangle, and the initial number in each cell.

Next come $n_1$ lines, each containing $m_1$ integers, describing the numbers in each cell of the small rectangle after the operations.

Next come $n_2$ lines, each containing $m_2$ integers, describing the numbers in each cell of the large rectangle after the operations.

The unknown number is replaced by $999999$.

Output Format

Output one line with one integer, which is the original value of the number marked as $999999$.

The testdata guarantees that a solution exists.

2 2 3 4 0
0 0
1 0
2 1 1 0
0 1 999999 0
0 0 0 0

2

Hint

For $40\%$ of the testdata, $n_1 = m_1 = 0$.

For $100\%$ of the testdata, $m_1 < m_2$, $0 \le n_1, m_1, k \le 100$, $1 \le n_2, m_2 \le 100$, and the number in each cell satisfies $-1000 \le$ value $\le 1000$. Besides the first $40\%$ of the testdata, the remaining $60\%$ of the testdata guarantees $n_1, m_1 > 0$.

Sample Explanation

At the beginning, the board is like this:

0 0
0 0
0 0 0 0
0 0 0 0
0 0 0 0

One possible sequence of operations is given below:

First, add $1$ to the number in row $2$ column $1$ and the number in row $3$ column $1$ at the same time:

0 0
1 0
1 0 0 0
0 0 0 0
0 0 0 0

Then, add $1$ to the number in row $3$ column $1$ and the number in row $3$ column $2$ at the same time:

0 0
1 0
2 1 0 0
0 0 0 0
0 0 0 0

Then, add $1$ to the number in row $3$ column $3$ and the number in row $4$ column $3$ at the same time:

0 0
1 0
2 1 1 0
0 0 1 0
0 0 0 0

Finally, add $1$ to the number in row $4$ column $2$ and the number in row $4$ column $3$ at the same time:

0 0
1 0
2 1 1 0
0 1 2 0
0 0 0 0

It can be concluded that the number marked as $999999$ (the number in row $4$ column $3$) is $2$.

The sequence of operations may not be unique, but it can be proven that the answer is unique.

Translated by ChatGPT 5