矩阵操作

题目来源

戳我

题目描述

有一个$n \times m$的整数矩阵A， 其中每个数字范围都在$[0, k)$

对于一次操作， 你可以执行下列两种操作中的一种

1. 对于任意一行$i$， 你可以把第$i$行中的所有数$A_{i, t}$变为$(A_{i, t}+1) \ mod \ k$

2. 对于任意一列$j$， 你可以把第$j$列中的所有数$A_{t, j}$变为$(A_{t, j}+1) \ mod \ k$

给定$n, m, k, A$

是否能通过若干次上面的操作， 将A变为全0矩阵， 如果可以， 输出最小操作数， 否则， 输出-1

输入格式

一行三个整数$1\leq n\leq 2000, 1\leq m \leq 2000, 1\leq k\leq 10^9$

接下来$n$行每行$m$个数， 表示矩阵A的初始状态

输出格式

一行， 如果可以输出操作数， 否则输出-1

样例输入 1

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

样例输出 1

2

样例输入 2

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

样例输出 2

-1