Problem 586: ducks

Enunț

Rațele sunt ființe maiestuase și foarte inteligente, dar, ca toate ființele, ele nu sunt perfecte. Lor le este foarte greu să se recunoască între ele.

Regatul PinkLand are o formă pătratică și este imparțit în $N \times N$ provincii. Fiecare provincie este condusă de un nobil a cărui putere este dată de numărul de rătuște din provincia lui. Notăm puterea provinciei de coordonate $(i, j)$ cu ${P_i}_j$ .

Regatul este condus de regele Duckie, care a venit cu o metodă ingenioasă pentru a fi mai ușor de recunoscut de celelalte rațe; el poartă o mantie roz. Din păcate, într-o zi, el se plimba prin pădurile din jurul regatului și, în timp ce stătea întins pe iarbă, pelerina lui a devenit verde. Acesta are la palatul său, care se află în parcela de coordonate $(N, N)$ o mantie de schimb, însă, ca să ajungă acolo, trebuie să treacă prin alte provincii. Acesta poate călători la fiecare pas în Nord, Sud, Est sau Vest cu condiția că nu va ieși din regat. El poate trece printr-o provincie doar dacă puterea lui este strict mai mare decât puterea nobilului din aceea provincie. Puterea unei provincii este egală cu numărul de rațe din aceea provincie. Mai grav! Din motive necunoscute puterea fiecărei provincii crește odată cu deplasarea regelui! Mai exact la momentul de timp $t$ , puterea provinciei de coordonate $(i, j)$ va fi ${P_i}_j + t \times {Q_i}_j$ . Deplasarea regelui se face într-o unitate de timp, iar momentul de timp inițial este $t_0 = 0$ . Cum inițial puterea lui este $0$ , cere ajutorul regelui Vilci din regatul Duckopolis sa îi trimită niște rațe care să îl insoțească până la palat, pentru a putea trece prin provincii. Regele Vilci acceptă, dar, din cauza faptului că drumul spre Duckie este păzit de renumitul vânător de rațe Chertes, el vrea să riște un număr cât mai mic de vieți pentru a-și ajuta prietenul. Ajutați-l pe Vilci să afle cel mai mic număr de rățuște care trebuie trimise.

O rațușcă trimisă de Vilci are puterea $1$ .

Cerință

Dându-se numerele naturale $T$ , $N$ și cate $T$ matrici de $N$ linii și $N$ coloane reprezantând numărul de rățuște din fiecare provincie a regatului PinkLand, afișați numărul minim de rățuște care trebuie trimise.

Date de intrare

În fișierul $ducks.in$ se vă afla $T$ , reprezentând numărul de teste. Pentru fiecare test, pe prima linie se vă afla numărul natural $N$ , iar pe următoarele $N$ linii se vor afla câte $N$ numere naturale, reprezentând puterea inițială a unei provincii, tabloul ${P_i}_j$ . Pe următoarele $N$ linii se vor afla câte $N$ numere naturale, reprezentând creșterea puterii fiecărei provincii, tabloul ${Q_i}_j$ .

Date de ieșire

În fișierul $ducks.out$ se va afișa T numere naturale $X$ , fiecare pe cate o linie, iar numarul natural $X$ de pe a i-a linie este numărul minim de rățuște pe care Vilci le va trimite să iși ajute prietenul lui, Duckie, la al i-lea test.

Restricții și precizări

$1 \leq T \leq 10$
$1 \leq N \leq 500$
$1 \leq {P_i}_j \leq10^{9}$ , $1 \leq i \leq N$ , $1 \leq j \leq N$ , unde ${P_i}_j$ reprezintă puterea nobilului din provincia de pe linia $i$ și coloana $j$ .
$1 \leq {Q_i}_j \leq10^{9}$ , $1 \leq i \leq N$ , $1 \leq j \leq N$ , unde ${Q_i}_j$ reprezintă creșterea puterii nobilului din provincia de pe linia $i$ și coloana $j$ .
Regele Duckie poate trece într-o provincie dacă la momentul de timp când ajunge în provincie puterea lui este strict mai mare decât puterea nobilului.
Pentru teste în valoare de $30p$ avem $1 \leq {P_i}_j, {Q_i}_j \leq 100$
Regele Duckie începe de la provincia din colțul (1, 1)

Exemplu

ducks.in

1
6
0 36 79 85 87 82
26 46 55 39 74 19
89 73 65 31 36 18
99 39 8 17 47 58
6 44 80 29 73 90
54 40 79 57 19 11
0 36 79 85 87 82
26 46 55 39 74 19
89 73 65 31 36 18
99 39 8 17 47 58
6 44 80 29 73 90
54 40 79 57 19 11

ducks.out

Marytone Contest | ducks