La un concurs de orientare turistică organizatorii au pregătit pentru participanţi un traseu, în care cele n*m puncte de control sunt plasate geografic în celulele unei matrice cu n linii şi m coloane. Participanţii nu sunt obligaţi să viziteze toate punctele de control, dar odată aflaţi într-un punct de control, trebuie să aleagă una dintre direcţiile oferite de acel punct.
Conform regulamentului, orice participant poate să intre pe teren din direcţia Nord (sus) şi trebuie să termine traseul ieşind pe partea sudică a traseului.
În fiecare punct de control participantul va primi puncte pozitive (recompensă) sau puncte negative (penalizare) şi trebuie să aleagă ca destinaţie un alt punct de control aflat într-una dintre direcţiile Est (dreapta), Vest (stânga) sau Sud (jos), însă el nu poate anticipa ce fel de puncte „îl vor aştepta” în următorul punct de control. Participantul niciodată nu are voie să se întoarcă într-un punct de control unde a mai fost odată.
Punctele câştigate sau pierdute se acumulează până ce participantul părăseşte traseul spre Sud.
Conform regulamentului jocului, participantul poate porni din orice punct de control din Nord şi poate ieşi din orice punct de control din Sud.
Cerinţă
Cunoscând harta traseului, să se calculeze punctajul maxim ce se poate obţine printr-o parcurgere optimă a traseului, precum şi numărul traseelor distincte pe care se pot obţine aceste punctaje maxime modulo 666013. Două trasee se consideră distincte, dacă diferă prin cel puţin un punct de control.
Date de intrare
Fişierul orientare.in conţine pe prima linie numerele naturale n şi m separate prin spaţiu, reprezentând numărul de linii şi respectiv numărul de coloane ale matricei. Următoarele n linii conţin câte m numere întregi separate prin spaţii, reprezentând punctajele corespunzătoare fiecărui punct de control.
Date de ieşire
Fişierul orientare.out va conţine două linii. Pe prima linie se va scrie suma maximă ce se poate câştiga pe traseu, iar pe linia a doua se va tipări numărul soluţiilor distincte de valoare maximă modulo 666013.
Restricţii
• Participantul se poate deplasa pe direcţiile Est şi Vest chiar şi pe prima şi ultima linie a matricei.
• 0 < n, m < 450
• Fiecare element al matricei se încadrează în intervalul [-255,255].
• Pentru 60% din teste 0 < n, m < 400.
• Afişarea corectă a sumei maxime valorează 60% din valoarea unui test, răspunsul corect la ambele cerinţe valorează 100% din valoarea testului.
Exemple
orientare.in
orientare.out
Explicaţii
3 3
5 -3 5
-1 6 -1
-3 4 -2
16
2
Suma maximă 16 se poate obţine în 2 moduri distincte.
