[翻譯][UVa][11793] Electoral Districts

在某些民主國家中,執政黨會重劃選區以便在下次選舉時對他們有利。每個選區選出一位代表,在兩黨制的政體中,每個地區選舉的票數只要高於對手即可。

某個國家被切割成 $N\times{N}$ 個正方形區域,這些區域將會被合併為 N 個選區,每個選區包含 N 個相連的區域,這代表著我們可以上、下、左、右,移動至選區內所有的區域。

假定執政黨為 A,在野黨為 B,從上一次的選舉中,我們可以知道每個區域的投票情況。現在給你兩個 $N\times{N}$ 的矩陣,第一個是政黨 A 的投票情況,第二個則是政黨 B 的投票情況,對於每個選區,我們將包含在內所有區域的票數取總和,這時總票數多的政黨將會贏得選舉,如果兩黨的票數一樣,則此選區不會被選出代表。

現在政黨 A 僱用你去計算出,在重劃選區的情況下,最大可能的代表數差。

輸入

輸入開始於一個整數 T,代表接下來的測試組數,每組測資間不以空白行隔開。對於每組測資第一行為一整數 N,代表一個國家的規模 (N 最大為 5,而此國家有 $N\times{N}$ 個區域),接著有 2N 行,每行有 N 個以空白格開介於 1 到 1000 的整數,前 N 行代表政黨 A 的票數,另外 N 行代表政黨 B 的票數。

輸出

輸出有 T 行,每組測資輸出一行,對於每組測資,請輸出可達到最大的代表總數的差值。

範例輸入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
4
2
2 3
2 4
3 1
2 3
3
2 3 4
1 3 2
2 3 5
3 4 1
3 2 1
2 1 3
3
1 2 1
2 1 2
1 2 1
2 1 2
1 2 1
2 1 2
3
1 1 1
1 1 1
1 1 1
2 2 2
2 2 2
2 2 2

範例輸出

1
2
3
4
2
2
1
-3
,