Matrix Operation

Problem Source

Click here

Problem Description

There is an $n \times m$ integer matrix $A$, where each number is in the range $[0, k)$.

In one operation, you may perform one of the following two types:

1. For any row $i$, change every number $A_{i, t}$ in that row to $(A_{i, t} + 1) \bmod k$.
2. For any column $j$, change every number $A_{t, j}$ in that column to $(A_{t, j} + 1) \bmod k$.

Given $n, m, k, A$, determine whether $A$ can be turned into the all-zero matrix by several such operations. If yes, output the minimum number of operations; otherwise output $-1$.

Input Format

One line with three integers $1 \le n \le 2000$, $1 \le m \le 2000$, $1 \le k \le 10^9$.

The next $n$ lines each contain $m$ numbers, representing the initial state of matrix $A$.

Output Format

One line: if possible, output the number of operations; otherwise output $-1$.

Sample Input 1

3 3 10
0 0 9
0 0 9
9 9 8

Sample Output 1

2

Sample Input 2

3 3 10
1 0 9
0 0 9
9 9 8

Sample Output 2

-1

Constraints

$1 \le n \le 2000$, $1 \le m \le 2000$, $1 \le k \le 10^9$.