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 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 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 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
• 1 ≤ L, C ≤ 1000
• Valorile din tablou sunt numere naturale mai mici sau egale cu 10000.
• Poteca unui copil nu poate trece prin casa sau grădiniţa celuilalt.
Exemple
poteci.in
poteci.out
Explicaţii
3 4
1 0 0 0
1 1 1 1
1 2 2 1
15
3 2
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).