poteci

Mergând către grădiniță, Mihai și Maria au observat că deseori ei se întâlnesc dimineața. Copiii nu frecventează aceeași grădiniță și nici nu locuiesc în apropiere pentru a pleca împreună. După ce s-au întâlnit și în această dimineață, ei s-au hotărât să stabilească, pentru fiecare, câte o potecă de acasă până la grădiniță, astfel încât potecile să se intersecteze și peisajul pe care îl pot admira de pe drumul lor să fie cât mai frumos. În plus, niciunul nu acceptă vreun ocol. Satul în care locuiesc cei doi copii poate fi reprezentat folosind un tablou cu $L$ linii (numerotate de la $1$ la $L$) și $C$ coloane (numerotate de la $1$ la $C$). Astfel, fiecare poziție din sat este dată de $2$ coordonate $(i, j)$, reprezentând, în ordine, linia și coloana poziției respective.

Casa lui Mihai este în poziția de coordonate $(1, 1)$ iar grădinița sa în poziția de coordonate $(L, C)$. Casa Mariei este în poziția de coordonate $(L, 1)$ iar grădinița sa în poziția de coordonate $(1, C)$. Fiecare copil poate face un pas din poziția curentă în oricare dintre cele $4$ poziții vecine pe linie sau pe coloană (fără a părăsi satul). Fiecărei poziții din tablou i se asociază o valoare naturală ce reprezintă “coeficientul de frumusețe al peisajului ce se poate vedea din poziția respectivă”. Pentru a determina coeficientul de frumusețe al unei poteci se însumează valorile din toate pozițiile prin care trece poteca.

Cerință

Determinați “coeficientul maxim de frumusețe” ce se poate obține pentru două poteci care să îndeplinească condițiile:

• să se intersecteze exact o dată, adică să aibă cel puțin o poziție comună în tablou (după intersectare, potecile pot continua pe poziții comune, dar după ce se separă nu trebuie să se mai intersecteze);
• poteca fiecărui copil trebuie să aibă număr minim de pași între casa și grădinița sa;
• numărul de poziții prin care trece poteca de la casa fiecăruia la locul de întâlnire poate fi diferit (primul dintre copii care ajunge în locul de întâlnire îl va aștepta și pe celălalt, valoarea din această poziție se contorizează o singură dată);
• suma pozițiilor din tablou de pe cele două poteci să fie maximă (valorile pozițiilor comune celor două poteci se adună de două ori).

Determinați de asemenea poziția în care cei doi se întâlnesc.

Date de intrare

Fișierul de intrare poteci.in conține pe prima linie cele două numere naturale $L$ și $C$, separate printr-un singur spațiu. Fiecare dintre următoarele $L$ linii conține câte $C$ numere naturale separate prin câte un spațiu, reprezentând coeficientul de frumusețe al peisajului ce poate fi admirat din poziția respectivă.

Date de ieșire

Fișierul de ieșire poteci.out va conține pe prima linie un număr natural ce reprezintă “coeficientul maxim de frumusețe”. A doua linie va conține două numere naturale $x$ și $y$, separate printr-un singur spațiu, reprezentând linia și coloana poziției în care potecile lor se intersectează. Dacă există mai multe astfel de poziții atunci se alege poziția în care valoarea liniei este minimă. Dacă și în acest caz sunt mai multe posibilități de alegere se alege poziția în care care valoarea coloanei este minimă.

Restricții și precizări

• $1 \leq L, C \leq 1 \ 000$
• Valorile din tablou sunt numere naturale mai mici sau egale cu $10 \ 000$
• Poteca unui copil nu poate trece prin casa sau grădiniţa celuilalt.
• Pentru determinarea corectă a primei cerinţe se acordă $30\%$ din punctaj.

Exemplu

poteci.in

3 4
1 0 0 0
1 1 1 1
1 2 2 1

poteci.out

15
3 2

Explicație

Poteca lui Mihai poate trece prin poziţiile, în această ordine: $(1, 1)$, $(2, 1)$, $(2, 2)$, $(3, 2)$, $(3, 3)$, $(3, 4)$.

Poteca Mariei poate trece prin poziţiile: $(3, 1)$, $(3, 2)$, $(3, 3)$, $(2, 3)$, $(2, 4)$, $(1, 4)$.