Problem 3381: Dulciuri

Pentru că astăzi este seara de Halloween, Vlad și Livia s-au costumat în solomonar și clarvăzătoare și au plecat după dulciuri. Ei pot porni din orice punct al Sighișoarei și pot termina în orice alt punct al orașului. Deoarece Sighișoara este aflată pe un deal, ei s-au decis să meargă doar spre Est sau spre Sud, adică în pantă; dacă ar urca dealul ar obosi prea rapid și nu ar mai speria pe nimeni.

Orașul este format dintr-un caroiaj de $N\times M$ case; oricare două case alăturate pe direcția Nord-Sud sau Est-Vest au o stradă care le separă. Adițional, există străzi și pe marginile orașului. Despre fiecare casă aflată la coordonate $(i, j)$ se știe cantitatea de dulciuri $D_{i,j}$ pe care locatarul său o oferă fiecărui copil.

Vlad și Livia au în schimb un truc secret prin care să facă oricare doi vecini să le dea mai multe bomboane: de fiecare dată când o iau pe o stradă ce trece printre două case, Livia bate la ușa uneia dintre case, Vlad la cealaltă și cantitatea de dulciuri primită devine magic produsul numărului de bomboane oferite de locatarii celor două case. Dezavantajul este că dacă merg pe la marginea orașului și trec pe lângă o singură casă, nu vor obține nicio bomboană de pe strada respectivă.

Cerință

Se cere să se calculeze numărul maxim de dulciuri pe care Vlad și Livia îl pot obține alegând un traseu optim printre case, deplasându-se doar pe direcțiile Est și Sud.

Date de intrare

Pe prima linie a intrării se află două numere întregi $N$ și $M$ , reprezentând numărul de linii, respectiv numărul de coloane ale orașului. Casa de la coordonatele $(1, 1)$ este cea mai Nord-Vestică a orașului.

Pe următoarele $N$ linii se găsesc câte $M$ valori întregi; a $j$ -a valoare de pe a $i$ -a dintre aceste linii reprezintă numărul de dulciuri $D_{i,j}$ oferite de casa de la coordonatele $(i, j)$ .

Date de ieșire

Afișați un singur număr întreg reprezentând numărul maxim de dulciuri pe care le pot obține Vlad și Livia alegând un traseu optim în această seară de Halloween.

Restricții și precizări

$1 \leq N,M \leq 1\ 800$
$1 \leq X \leq 10\ 000$

#	Punctaj	Restricții
1	17	$1 \leq N, M \leq 10$
2	24	$1 \leq N, M \leq 80$
3	27	$1 \leq N, M \leq 300$
4	32	Fără restricții adiționale.

Exemplu

stdin

2 4 5 2 3 2
4 5 2 3 2 1
7 2 9 10 3 5
1 8 10 20 4 6
11 1 2 5 10 1
12 3 4 6 10 2

stdout

Explicație

$4\times7+7\times2+2\times8+9\times10+10\times20$ $+\ 20\times5+5\times10+10\times10+10\times2 + 2\times0 = 618$

Dulciuri