← 返回题目列表

AtCoder · arc133_c

C. 行列总和

中文机器翻译题面 查看原题

分数: 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