题目描述

我们有一个 $H$ 行 $W$ 列的网格。

Snuke 将在每个方块中写入一个介于 $0$ 到 $K-1$（包含边界）之间的整数。这里，必须满足以下条件：

• 对于每个 $1 \\leq i \\leq H$，第 $i$ 行中写入的整数的模 $K$ 的和为 $A_i$。
• 对于每个 $1 \\leq i \\leq W$，第 $i$ 列中写入的整数的模 $K$ 的和为 $B_i$。

确定是否可以写入整数以满足条件。如果可能，还要找出可写整数的最大可能和。

约束条件

• $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$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$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

示例输出1

11

应该写入如下内容：

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

我们可以看到满足了条件。例如，第一行中整数的和是 $6$，模 $K(=3)$ 的结果是 $A_1(=0)$。

这里写入的整数的和为 $11$，这是可行的最大值。

示例输入2

3 3 4
0 1 2
1 2 3

示例输出2

-1