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 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 cu .
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 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 , puterea provinciei de coordonate va fi . Deplasarea regelui se face într-o unitate de timp, iar momentul de timp inițial este . Cum inițial puterea lui este , 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 .
Cerință
Dându-se numerele naturale , și cate matrici de linii și 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 se vă afla , reprezentând numărul de teste. Pentru fiecare test, pe prima linie se vă afla numărul natural , iar pe următoarele linii se vor afla câte numere naturale, reprezentând puterea inițială a unei provincii, tabloul . Pe următoarele linii se vor afla câte numere naturale, reprezentând creșterea puterii fiecărei provincii, tabloul .
Date de ieșire
În fișierul se va afișa T numere naturale , fiecare pe cate o linie, iar numarul natural 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
- , , , unde reprezintă puterea nobilului din provincia de pe linia și coloana .
- , , , unde reprezintă creșterea puterii nobilului din provincia de pe linia și coloana .
- 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 avem
- 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
514