Vera érdekes játékot telepített a újonnan vett mobiljára. Ebben a játékban adott egy \(A\) mátrix \(N\) sorral és \(M\) oszloppal. A cél az, hogy maximalizáljuk a mátrix szépségét. A mátrix szépségét úgy kapjuk, hogy a szomszédos mezők különbségét képezzük, majd az így kapott számokat abszolút értékben összeadjuk. Szomszédos mezők azok, amelyeknek van közös oldala. Pontosan meghatározva a mátrix szépségét a

\(\sum_{i=0}^{i<N-1} \sum_{j=0}^{j<M} |A[i+1][j]-A[i][j]| + \sum_{j=0}^{j<M-1} \sum_{i=0}^{i<N} |A[i][j+1]-A[i][j]|\) kifejezés adja.

Az \(A[i][j]\) az \(A\) mátrix az \(i\)-edik sorának és \(j\)-edik oszlopának eleme.

Vera a mátrixon a következő változtatásokat hajthatja végre:

• A telefonját balra mozdítja, és ezzel ciklikusan elmozgatja az összes sor elemeit balra egy hellyel, vagyis az \(A[i][j]\) elem az az elem lesz, amely az elmozgatás előtt \(A[i][(j+1) \mod M]\) elem volt (\(0 \leq i < N\) és \(0 \leq j < M\)).
• A telefonját felfelé mozdítja, és ezzel ciklikusan elmozgatja az összes oszlop elemeit felfelé egy hellyel, vagyis: az \(A[i][j]\) elem az az elem lesz, amely az elmozgatás előtt \(A[(i+1) \mod N][j]\) elem volt (\(0 \leq i < N\) és \(0 \leq j < M\)).

Vera ezeket a műveleteket többször elvégezheti, tetszőleges sorrendben. Segítsetek neki, hogy kiírassa a mátrix lehető legnagyobb szépségét.

Bemenet

A szabványos bemenet első sorában az \(N\) és \(M\) egész számok helyezkednek el. Az \(N\) az \(A\) mátrix sorainak, az \(M\) pedig az oszlopainak számát képviseli. A következő \(N\) sorban \(M\) egész szám található, ahol az \(i\)-edik sorban található \(j\)-edik szám épp az \(A[i][j]\) elem.

Kimenet

A kimenet egyetlen sorában kiíratni egyetlen számot, a mátrix legnagyobb lehetséges szépségét.

Korlátozások

• \(1 \leq N,M \leq 1.000\)
• \(1 \leq A[i][j] \leq 10^9\), minden \(0 \leq i < N\) és \(0 \leq j < M\)

A tesztpéldák 5 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: \(N = 1\).

• Tesztpéldák, melyek \(10\) pontot érnek: \(N, M \leq 100\).

• Tesztpéldák, melyek \(20\) pontot érnek: \(N, M \leq 500\).

• Tesztpéldák, melyek \(20\) pontot érnek: \(A[i][j] \leq 2\), minden \(0 \leq i < N\) és \(0 \leq j < M.\)

• Tesztpéldák, melyek \(40\) pontot érnek: nincs külön korlátozás.

Példák

1. példa

Bemenet

3 3
2 1 1
1 1 1
1 1 1

Kimenet

4

Magyarázat

Először balra mozdítjuk a telefont, és a következő mátrixot kapjuk.

1 1 2
1 1 1
1 1 1

Ezután kétszer felfelé mozdítjuk a telefont, és a következő mátrixot kapjuk.

1 1 1
1 1 2
1 1 1

A végén még egyszer balra mozdítjuk a telefont, és a következő mátrixot kapjuk, amelynek a szépsége 4.

1 1 1
1 2 1
1 1 1