C - Row Column Sums Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 と出力せよ． 可能な場合，書き込む整数の総和としてありうる最大値を出力せよ．

入力例 1

2 4 3
0 2
1 2 2 0

出力例 1

11

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

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

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

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

入力例 2

3 3 4
0 1 2
1 2 3

出力例 2

-1

Score : 500 points

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