配点 : $500$ 点

問題文

$H$ 行 $W$ 列からなるマス目があります．

すぬけくんは，各マスに $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 と出力せよ． 可能な場合，書き込む整数の総和としてありうる最大値を出力せよ．

2 4 3
0 2
1 2 2 0

11

以下のように書き込めば良いです．

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

この書き方は条件を満たしています． 例えば $1$ 行目に書かれた整数の総和は $6$ であり，これを $K(=3)$ で割ったあまりは $A_1(=0)$ になっています．

この書き方では整数の総和は $11$ になっており，これはありうる最大値です．

3 3 4
0 1 2
1 2 3

-1