시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB544100.000%

문제

Two m×n matrices A and B are given. Matrix B is obtained from matrix A by row-addition operations and column-subtraction operations. A row-addition operation adds 1 to each entry of a row. A column-subtraction operation subtracts 1 from each entry of a column.

In this task, you have to find the numbers of row-addition operations r1, · · ·, rm to be applied to row 1, · · ·, row m of A respectively such that the following properties hold.

  • There correspond c1, · · ·, cn column-subtraction operations to be applied to column 1, · · ·, column n of A respectively so that these row and column operations transform the given matrix A to the given matrix B.
  • The number of any row and column operations is between 0 and 9 inclusively; that is, 0 ≤ ri ≤ 9, i = 1, · · · , m and 0 ≤ cj ≤ 9, j = 1, · · · , n.
  • The value r1 · · · rm, considered as an integer, is as small as possible.

You should concatenate the values r1, · · ·, rm and output it as a single m-digit integer r1 · · · rm (with possibly leading zeros). If the given matrix B cannot be obtained from the given matrix A with 0 to 9 row-addition operations on each row and 0 to 9 column-subtraction operations on each column, your program should output the value −1.

입력

The first line contains two integers m and n separated by a space, 1 ≤ m ≤ 100, 1 ≤ n ≤ 100. The matrix A is given by the next m lines for row 1 to row m. Each of these m lines contains n integers, with a space between two adjacent integers. Similarly, the matrix B is given by the next m lines. Each entry of the matrices is an integer between −1000 and 1000 inclusively.

출력

The output file contains an m-digit integer.

예제 입력 1

2 3
1 2 3
4 5 6
1 0 0
0 -1 -1

예제 출력 1

40

Let

\[A = \begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}, B = \begin{bmatrix}1&0&0\\0&-1&-1\end{bmatrix}\text{.}\]

The required row-additions and column-subtractions are shown as:

\[ \begin{array}{c|ccc} &-4&-6&-7 \\ \hline +4 & 1 & 2 & 3 \\ +0 & 4 & 5 & 6 \end{array} \]

Since there are 4 and 0 row-additions operations for row 1 and row 2 respectively, the required output is

\[40\]

after checking that 4 is the smallest possible number of row operations for row 1.

예제 입력 2

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

예제 출력 2

420

Let

\[A = \begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}, B = \begin{bmatrix}1&4&7\\2&5&8\\3&6&9\end{bmatrix}\text{.}\]

The required row-additions and column-subtractions are shown as:

\[ \begin{array}{c|ccc} &-4&-2&-0 \\ \hline +4 & 1 & 2 & 3 \\ +2 & 4 & 5 & 6 \\ +0 & 7 & 8 & 9 \end{array} \]

Since there are 4, 2, and 0 row-additions operations for row 1, row 2, and row 3, the required output is

\[420\]

after checking that 4 is the smallest possible number of row operations for row 1.

예제 입력 3

2 1
0
-9
9
9

예제 출력 3

-1

Let

\[A = \begin{bmatrix}0\\-9\end{bmatrix}, B = \begin{bmatrix}9\\9\end{bmatrix}\text{.}\]

It can be checked that it is impossible to obtain B from A with 0 to 9 row-additions on each row and 0 to 9 column-subtractions on each column. So the output should be −1.