Problem Statement

We have a grid with $H$ rows and $W$ columns.

Snuke is going to write in each square an integer between $0$ and $K-1$ (inclusive). Here, the conditions below must be satisfied.

• For each $1 \\leq i \\leq H$, the sum modulo $K$ of the integers written in the $i$-th row is $A_i$.
• For each $1 \\leq i \\leq W$, the sum modulo $K$ of the integers written in the $i$-th column is $B_i$.

Determine whether it is possible to write integers in the squares to satisfy the conditions. If it is possible, also find the maximum possible sum of the integers written.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If it is impossible to write integers in the squares to satisfy the conditions, print -1. If it is possible, print the maximum possible sum of the integers written.

Sample Input 1

2 4 3
0 2
1 2 2 0

Sample Output 1

11

The following should be written.

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

We can see that the conditions are satisfied. For example, the sum of the integers in the $1$-st row is $6$, which modulo $K(=3)$ is $A_1(=0)$.

The sum of the integers written here is $11$, which is the maximum possible value.

Sample Input 2

3 3 4
0 1 2
1 2 3

Sample Output 2

-1