该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

有一个由 $H$ 行 $W$ 列组成的矩阵。

给每个 $a_{ij}$ 填入一个 [0, k) 之间的整数。使得：

每一行的行和除以 $k$ 的余数是指定值。

每一列的列和除以 $k$ 的余数是指定值。

求矩阵所有元素和的最大值。

如果不存在，则输出 -1 。

Format

Input

第一行三个不超过 200000 的正整数： $H$ 、 $W$ 和 $K$ 。

第二行给出每个行和除以 $K$ 的余数 。

第三行给出每个列和除以 $K$ 的余数 。

Output

在一行中输出答案。

Samples

2 4 3
0 1
0 2 2 0

10

Limitation

1s, 1024KiB for each test case.