canal

Un sat ia forma unei matrice $A$ cu liniile numerotate de la $1$ la $N$ și coloanele numerotate de la $1$ la $M$. Fiecare celulă $(i, j)$ este ori liberă, lucru semnalat prin $A[i][j] = 0$, ori conține o casă cu $|A[i][j]|$ locuitori. Dacă $A[i][j] > 0$, casa este roz, iar dacă $A[i][j] < 0$, este vișinie.

Voi va trebui să construiți un canal cu apă care pleacă din celula $(1, 1)$ și ajunge în celula $(N, M)$ mergând pe patru direcții (adică nord, sud, est și vest). Canalul nu are voie să treacă prin case sau să iasă din matrice și trebuie să fie de lungime minimă. Formal, canalul este o succesiune de celule din matrice $(\ell_1, c_1) \rightarrow (\ell_2, c_2) \rightarrow \ldots \rightarrow (\ell_k, c_k)$ astfel încât:

• $(\ell_1, c_1) = (1, 1)$;
• $(\ell_k, c_k) = (N, M)$;
• Pentru $1 \leq i < k$ celulele $(\ell_i, c_i)$ și $(\ell_{i + 1}, c_{i + 1})$ au o latură comună;
• $k$ este minim.

Se garantează că există cel puțin un canal.

Un canal $(\ell_1, c_1) \rightarrow (\ell_2, c_2) \rightarrow \ldots \rightarrow (\ell_k, c_k)$ împarte satul unic în două sectoare. Sectorul nord-estic conține celulele din afara canalului aflate pe prima linie și ultima coloană a matricei, dar și celulele în care se poate ajunge din acestea mergând pe opt direcții (nord, sud, est, vest, nord-est, nord-vest, sud-est și sud-vest) fără a ieși din matrice sau a trece prin celule ale canalului. Formal, o celulă $(i, j)$ aparține sectorului nord-estic dacă există o succesiune de celule din afara canalului $(i_1, j_1) \rightarrow \ldots \rightarrow (i_t, j_t)$ astfel încât:

• $(i_1, j_1) = (i, j)$;
• $i_t = 1$ sau $j_t = M$;
• Pentru $1 \leq q < t$ celulele $(i_q, j_q)$ și $(i_{q + 1}, j_{q + 1})$ au o latură comună sau un vârf comun.
• Atenție! Celulele succesiunii (inclusiv prima și ultima) pot să fie case.

Sectorul sud-vestic se definește complet analog plecând de la celulele de pe prima coloană și ultima linie. Se poate demonstra că toate celulele din afara canalului fac parte fie din sectorul nord-estic, fie din cel sud-vestic.

Locuitorii unei case vișinii sunt fericiți dacă casa se află în sectorul nord-estic, iar locuitorii unei case roz sunt fericiți dacă casa se află în sectorul sud-vestic.

Să se calculeze numărul de celule dintr-un canal $k$ și, dintre toate canalele posibile, numărul total maxim de oameni fericiți $X$.

Date de intrare

Pe prima linie se află $N$ și $M$, dimensiunile matricei, separate printr-un spațiu.

Pe următoarele $N$ linii se află matricea $A$: a $i$-a dintre acestea va conține $A[i][1], \ldots, A[i][M]$, oricare două elemente consecutive fiind separate prin câte un spațiu.

Date de ieșire

Se vor afișa pe o singură linie cele două numere $k$ și $X$, separate printr-un spațiu.

Restricții

• $1 \leq N, M \leq 2 \ 000$
• $-1 \ 000 \ 000 \ 000 \leq A[i][j] \leq 1 \ 000 \ 000 \ 000$ pentru $1 \leq i \leq N$ și $1 \leq j \leq M$.
• Deoarece trebuie citite multe numere, vă recomandăm folosirea std::ios_base::sync_with_stdio(false); std::cin.tie(0); ca primă linie în funcția main() , pentru a face citirea mai rapidă.

Exemplul 1

stdin

5 5
0 -1 0 0 0
0 0 0 1 0
0 1 0 1 0
0 1 0 0 0
0 0 0 1 0

stdout

9 4

Explicație

În acest exemplu avem $N = M = 5$. Există un singur canal, format din $k = 9$ celule, desenat mai jos cu albastru. În poza stânga, casele sunt colorate cu roz și vișiniu, iar în cea din dreapta vedem sectorul nord-estic evidențiat cu alabastru hașurat, iar cel sud-vestic cu verde hașurat. Toți cei 3 oameni din sectorul sud-vestic sunt fericiți, iar din sectorul nord-estic doar un singur om este fericit, de unde $X = 3 + 1 = 4$.

Exemplul 2

stdin

5 6
0 0 -1 0 0 0
1 0 1 0 8 0
0 0 1 0 7 0
0 4 0 0 6 0 
0 0 0 -2 5 0

stdout

20 28

Explicație