Lýsing

JOI-kun er að leika sér í teikniforriti.

Í teikniforritinu er hægt að teikna mynd á rétthyrnt grindanet með $H$ röðum lóðrétt og $W$ dálkum lárétt. Hver reitur hefur ákveðinn lit og litirnir eru táknaðir með heiltölum frá $1$ til $10^9$, að báðum töluðum.

Reiturinn í $i$-tu röð að ofan ($1 \le i \le H$) og $j$-ta dálki frá vinstri ($1 \le j \le W$) kallast reitur $(i,j)$. Núna er liturinn á reit $(i,j)$ jafn $A_{i,j}$.

Mengi þeirra reita sem hægt er að komast á frá reit $(i,j)$ með því að færa sig endurtekið yfir á reit sem deilir hlið, án þess að fara nokkurn tímann inn á reit sem hefur annan lit en reitur $(i,j)$, kallast hér svæði reits $(i,j)$.

Teikniforritið er með eiginleika sem kallast fylling (flood fill). Með þessum eiginleika breytist litur allra reita sem eru í svæði reits $(x,y)$ í $c$ þegar tiltekinn reitur $(x,y)$ ($1 \le x \le H$, $1 \le y \le W$) og litur $c$ ($1 \le c \le 10^9$) eru tilgreind.

JOI-kun velur tiltekinn reit $(x,y)$ og lit $c$, og notar fyllingu með þeim reit og lit nákvæmlega $1$ sinni. Fjöldi reita sem eru í svæði reits $(x,y)$ eftir að fyllingin hefur verið notuð verður stigafjöldi JOI-kun.

Skrifið forrit til að finna hæsta mögulega stigafjölda sem JOI-kun getur náð.

Inntak

Inntakið er gefið á eftirfarandi sniði:

H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
:
A_{H,1} A_{H,2} \ldots A_{H,W}

Úttak

Prentið í $1$ línu hæsta mögulega stigafjölda sem JOI-kun getur náð.

Takmarkanir

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $1 \le A_{i,j} \le 10^9$ ($1 \le i \le H$, $1 \le j \le W$).
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($9$ stig) $H = 1$.
2. ($32$ stig) $H \le 30$, $W \le 30$, $A_{i,j} \le 5$ ($1 \le i \le H$, $1 \le j \le W$).
3. ($18$ stig) $H \le 30$, $W \le 30$.
4. ($10$ stig) $A_{i,j} \le 2$ ($1 \le i \le H$, $1 \le j \le W$).
5. ($31$ stig) Engar viðbótartakmarkanir.

Dæmi

Inntaksdæmi 1

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

Úttaksdæmi 1

9

Í upphafi eru $4$ reitir í svæði reits $(2,2)$, sem eru reitirnir $(1,2), (2,1), (2,2), (3,2)$. Því breytist litur þessara $4$ reita í $3$, eins og sýnt er á myndinni hér að neðan, ef fylling er notuð með því að tilgreina reit $(2,2)$ og lit $3$.

Eftir að fyllingin hefur verið notuð eru $9$ reitir í svæði reits $(2,2)$, sem eru reitirnir $(1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2)$. Þannig verður stigafjöldi JOI-kun $9$.

Þar sem ekki er hægt að láta stigafjölda JOI-kun verða $10$ eða meira er prentað $9$.

Þetta inntak uppfyllir takmarkanir undirverkefna $2, 3, 5$.

Inntaksdæmi 2

2 10
1 2 2 1 3 3 3 3 1 1
1 1 1 1 1 1 1 3 3 3

Úttaksdæmi 2

18

Þetta inntak uppfyllir takmarkanir undirverkefna $2, 3, 5$.

Inntaksdæmi 3

5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Úttaksdæmi 3

25

Þetta inntak uppfyllir takmarkanir undirverkefna $2, 3, 4, 5$.