#P18258. Godzilla
Godzilla
Godzilla
古老的泰坦巨兽 Godzilla 正在前往 Bytetown!
Bytetown 有 个街区,从上方看形成一个 行 列的网格。行、列分别从 到 、从 到 编号。
Godzilla 会恰好访问每个街区一次。当他位于街区 时,可以不做任何事,或者消耗 单位能量,选择以下一种攻击:
- 发动“水平原子吐息”,击中第 行的所有街区;
- 发动“竖直原子吐息”,击中第 列的所有街区。
两种攻击造成的伤害值均为 。Godzilla 不会在同一个街区发动多次攻击。
Godzilla 残暴却公平:每个街区必须恰好被水平原子吐息击中一次,也恰好被竖直原子吐息击中一次。
对于 ,分别求出:当消耗的总能量对 取模等于 时,Godzilla 能够造成的最大总伤害。如果某种余数无法达到,输出 。
可以认为 Godzilla 始终有足够能量,除了总能量的余数要求外,没有其他能量上限。
输入格式
第一行包含两个整数 ,表示行数和列数。
接下来 行,第 行包含 个整数 ,表示在各街区发动攻击的伤害值。
再接下来 行,第 行包含 个整数 ,表示在各街区发动攻击消耗的能量。
输出格式
输出四行。第 行()输出一个整数,表示总能量对 取模为 时的最大总伤害;无法达到该余数时输出 。
数据范围
- ;
- ;
- ;
- 输入只有一组数据。
样例 1
2 2
1 2
3 4
2 1
0 3
-1
-1
10
-1
样例 2
3 3
1 2 3
4 5 6
7 8 9
2 1 0
0 3 2
1 2 1
35
38
37
36