#P18258. Godzilla

Godzilla

Godzilla

古老的泰坦巨兽 Godzilla 正在前往 Bytetown!

Bytetown 有 n×mn\times m 个街区,从上方看形成一个 nn 行 mm 列的网格。行、列分别从 11 到 nn、从 11 到 mm 编号。

Godzilla 会恰好访问每个街区一次。当他位于街区 (i,j)(i,j) 时,可以不做任何事,或者消耗 e(i,j)e(i,j) 单位能量,选择以下一种攻击:

  • 发动“水平原子吐息”,击中第 ii 行的所有街区;
  • 发动“竖直原子吐息”,击中第 jj 列的所有街区。

两种攻击造成的伤害值均为 d(i,j)d(i,j)。Godzilla 不会在同一个街区发动多次攻击。

Godzilla 残暴却公平:每个街区必须恰好被水平原子吐息击中一次,也恰好被竖直原子吐息击中一次。

对于 k=0,1,2,3k=0,1,2,3,分别求出:当消耗的总能量对 44 取模等于 kk 时,Godzilla 能够造成的最大总伤害。如果某种余数无法达到,输出 −1-1。

可以认为 Godzilla 始终有足够能量,除了总能量的余数要求外,没有其他能量上限。

输入格式

第一行包含两个整数 n,mn,m,表示行数和列数。

接下来 nn 行,第 ii 行包含 mm 个整数 d(i,1),…,d(i,m)d(i,1),\ldots,d(i,m),表示在各街区发动攻击的伤害值。

再接下来 nn 行,第 ii 行包含 mm 个整数 e(i,1),…,e(i,m)e(i,1),\ldots,e(i,m),表示在各街区发动攻击消耗的能量。

输出格式

输出四行。第 ii 行(1≤i≤41\le i\le4)输出一个整数,表示总能量对 44 取模为 i−1i-1 时的最大总伤害;无法达到该余数时输出 −1-1。

数据范围

  • 2≤n,m≤752\le n,m\le75;
  • 1≤d(i,j)≤1071\le d(i,j)\le10^7;
  • 0≤e(i,j)≤30\le e(i,j)\le3;
  • 输入只有一组数据。

样例 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