walk

On vous donne une matrice d'entiersM composée de n lignes, et n colonnes. Le but est de faire une marche sur les cellules de la matrice, qui maximise la somme totale des valeurs de cellules visitées, sous les contraintes suivantes:

Le fichier commence avec T le nombre de testcases. Chaque testcase contient alors un entier n la taille de la matrice. Puis n lignes de n nombre M_ij. La ième ligne contient les entiers M_i1, M_i2,...,M_in

Limites et formatage

Chaque réponse commencera par Case #i: avec i le numéro du testcase (en commencant à 1). Votre programme doit retourner le bon résulat en moins de 10 secondes compilé avec -O2 sur une des machines de l'école.

Input

10
4
2 -2 -2 -1 
-1 -2 1 0 
-2 0 -2 1 
0 -1 1 -1 
2
1 0 
1 -1 
4
-2 0 -1 1 
0 2 2 2 
0 2 1 -1 
-1 -1 0 2 
3
-2 -1 0 
2 2 2 
-1 1 0 
2
0 2 
2 1 
2
-1 2 
2 2 
2
2 -2 
2 0 
3
0 2 0 
0 0 -1 
-2 0 -1 
2
1 -2 
0 -2 
3
-1 -2 2 
-1 -1 -2 
1 2 1 

Télécharger l'entrée

Output

Case #1: -4
Case #2: 1
Case #3: 8
Case #4: 4
Case #5: 5
Case #6: 5
Case #7: 2
Case #8: 0
Case #9: -3
Case #10: 0

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.