raze

Harta digitală a câmpului de luptă este memorată într-un tablou bidimensional cu $N$ linii, $M$ coloane și elemente din mulțimea {$0,1$}. Valoarea $0$ reprezintă o poziție liberă, iar valoarea $1$ reprezintă o poziție ocupată de un obstacol. În fiecare element aflat pe conturul tabloului, adică pe prima linie, prima coloana, ultima linie și ultima coloană, se află obiective inamice. Pe conturul tabloului se găsesc numai elemente nule.

În interiorul tabloului (elementele care nu se află pe contur), într-o poziție liberă, trebuie plasat un soldat. Scopul său este să anihileze cât mai multe obiective inamice. Din păcate, el deține o armă laser cu care poate executa doar un singur atac. La lansarea atacului, se trimit $4$ raze, câte una în fiecare dintre cele $4$ direcții diagonale. O rază poate merge până la întâlnirea unui obstacol (în acest caz se oprește și nu va avea nici un efect) sau până ajunge pe contur (în acest caz distruge obiectivul inamic respectiv).

Cerință

Scrieți un program care determină numărul maxim de obiective inamice, notat cu $K$, ce pot fi distruse în urma unui atac, precum și numărul pozițiilor în care putem plasa soldatul pentru a distruge $K$ obiective inamice.

Date de intrare

Fișierul de intrare raze.in conține pe prima linie numărul natural $T$, reprezentând numărul seturilor de date de intrare. Pentru fiecare set de date de intrare în fișierul de intrare pe prima linie a setului se află numerele naturale $N$ și $M$, separate printr-un spațiu, reprezentând numărul liniilor, respectiv numărul coloanelor tabloului; pe următoarele $N$ linii ale setului de date se află câte M numere naturale din mulțimea {$0,1$}, separate prin câte un spațiu, reprezentând forma digitală a hărții câmpului de luptă.

Date de ieșire

Fișierul de ieșire raze.out va conține $T$ linii, corespunzătoare celor $T$ seturi de date de intrare. Pe fiecare linie se vor tipări două numere naturale $K$ și $P$, separate printr-un spațiu, reprezentând numărul maxim de obiective inamice distruse în atac, respectiv numărul pozițiilor din care se pot distruge $K$ obiective inamice.

Restricții și precizări

• $1 \leq T \leq 80$
• $3 \leq N, M \leq 135$
• Se garantează că există cel puțin un obiectiv inamic ce poate fi anihilat pentru fiecare set de date de intrare.

Exemplu

raze.in

2
4 6
0 0 0 0 0 0
0 0 1 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0
4 7
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

raze.out

4 1
3 2

Explicație

În fișier se găsesc două seturi de date de intrare.
În primul set de date se pot anihila maximum $4$ obiective inamice, poziționând soldatul în linia $2$ și coloana $2$.
În al doilea set de date se pot anihila maximum $3$ obiective inamice, poziționând soldatul în elementul de pe linia $3$ și coloana $2$ sau în elementul din linia $3$ și coloana $6$.