行列和

时间限制：2s
空间限制：1024MB

题目描述

有一个 $H$ 行 $W$ 列的网格。你需要在每个格子中写入一个 $0$ 到 $K-1$ 之间的整数，并满足：第 $i$ 行所有数之和除以 $K$ 的余数为 $A_i$，第 $j$ 列所有数之和除以 $K$ 的余数为 $B_j$。

判断是否存在满足条件的填写方案；若存在，求所有格子中整数总和的最大值。

输入格式

H W K
A_1 A_2 ... A_H
B_1 B_2 ... B_W

输出格式

若不存在方案，输出 -1；否则输出可能的最大总和。

样例输入 1

2 4 3
0 2
1 2 2 0

样例输出 1

11

样例输入 2

3 3 4
0 1 2
1 2 3

样例输出 2

-1

数据范围

• $1\le H,W\le 200000$；
• $2\le K\le 200000$；
• $0\le A_i,B_j<K$；