分数: 500 点
问题陈述
我们有一个网格 H 行和 W 列。
Snuke 将在每个方格中写入一个整数 0 和 K-1 (含)。 这里,必须满足以下条件。
- 对于每个 1 \leq i \leq H,模数之和 K 中写入的整数 i- 第行是 A_i.
- 对于每个 1 \leq i \leq W,模数之和 K 中写入的整数 i第列是 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 | -----------------
我们可以看到条件已经满足。 例如,中的整数之和 1-st 行是 6,模 K(=3) is A_1(=0).
这里写入的整数之和是 11,这是最大可能值。
示例输入 2
3 3 4 0 1 2 1 2 3
示例输出 2
-1