题目描述

有一个由 $H$ 行 $W$ 列组成的格子。

すぬけくん打算在每个格子里填写一个 $0$ 到 $K-1$ 之间的整数。需要满足以下条件：

• 对于每个 $1 \leq i \leq H$，第 $i$ 行所有格子中填写的整数之和除以 $K$ 的余数为 $A_i$。
• 对于每个 $1 \leq i \leq W$，第 $i$ 列所有格子中填写的整数之和除以 $K$ 的余数为 $B_i$。

请判断是否存在一种填写方式满足上述条件。如果存在，请求出所有格子中填写的整数之和的最大可能值。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$ $K$ $A_1$ $A_2$ $\cdots$ $A_H$ $B_1$ $B_2$ $\cdots$ $B_W$

输出格式

如果不存在满足条件的填写方式，输出 -1。如果存在，输出所有格子中填写的整数之和的最大可能值。

样例 1

输入

2 4 3
0 2
1 2 2 0

输出

11

样例 2

输入

3 3 4
0 1 2
1 2 3

输出

-1

说明/提示

限制

• $1 \leq H, W \leq 200000$
• $2 \leq K \leq 200000$
• $0 \leq A_i \leq K-1$
• $0 \leq B_i \leq K-1$
• 输入的所有数均为整数

样例解释 1

可以如下填写：

-----------------
| 2 | 0 | 2 | 2 |
-----------------
| 2 | 2 | 0 | 1 |
-----------------

这种填写方式满足条件。例如，第 $1$ 行填写的整数之和为 $6$，用 $K(=3)$ 除后余数为 $A_1(=0)$。这种填写方式下所有整数之和为 $11$，这是可能的最大值。

由 ChatGPT 4.1 翻译