Beskrivelse

JOI-kun leker med et tegneprogram.

I tegneprogrammet kan man tegne et bilde på et rektangulært rutenett med $H$ rader loddrett og $W$ kolonner vannrett. Hver rute har en bestemt farge, og fargene representeres av heltall mellom $1$ og $10^9$, inkludert.

Ruten i den $i$-te raden ovenfra ($1 \le i \le H$) og den $j$-te kolonnen fra venstre ($1 \le j \le W$) kalles rute $(i,j)$. For øyeblikket er fargen på rute $(i,j)$ lik $A_{i,j}$.

Mengden ruter som kan nås fra rute $(i,j)$ ved gjentatte ganger å flytte til en rute som deler en sidekant, uten å gå inn i noen rute med en annen farge enn rute $(i,j)$, kalles her området til rute $(i,j)$.

Tegneprogrammet har en funksjon som kalles fylling. Med denne funksjonen endres fargen på alle rutene i området til rute $(x,y)$ til $c$ når man angir en bestemt rute $(x,y)$ ($1 \le x \le H$, $1 \le y \le W$) og en farge $c$ ($1 \le c \le 10^9$).

JOI-kun velger en bestemt rute $(x,y)$ og en farge $c$, og bruker fylling ved å angi denne ruten og fargen nøyaktig $1$ gang. Antallet ruter i området til rute $(x,y)$ etter bruk av fylling blir JOI-kuns poengsum.

Skriv et program som finner den høyeste mulige poengsummen JOI-kun kan oppnå.

Inndata

Inndataene gis i følgende format:

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}

Utdata

Skriv ut på $1$ linje den høyeste mulige poengsummen JOI-kun kan oppnå.

Begrensninger

• $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$).
• Alle inndataverdier er heltall.

Deloppgaver

1. ($9$ poeng) $H = 1$.
2. ($32$ poeng) $H \le 30$, $W \le 30$, $A_{i,j} \le 5$ ($1 \le i \le H$, $1 \le j \le W$).
3. ($18$ poeng) $H \le 30$, $W \le 30$.
4. ($10$ poeng) $A_{i,j} \le 2$ ($1 \le i \le H$, $1 \le j \le W$).
5. ($31$ poeng) Ingen ytterligere begrensninger.

Eksempler

Eksempel på inndata 1

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

Eksempel på utdata 1

9

På starttidspunktet er det $4$ ruter i området til rute $(2,2)$, nemlig rutene $(1,2), (2,1), (2,2), (3,2)$. Derfor, hvis man bruker fylling ved å angi rute $(2,2)$ og farge $3$, endres fargen på disse $4$ rutene til $3$ som vist i figuren nedenfor.

Etter bruk av fylling er det $9$ ruter i området til rute $(2,2)$, nemlig rutene $(1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2)$. Dermed blir JOI-kuns poengsum $9$.

Siden JOI-kuns poengsum ikke kan bli $10$ eller mer, skrives $9$ ut.

Disse inndataene oppfyller begrensningene i deloppgavene $2, 3, 5$.

Eksempel på inndata 2

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

Eksempel på utdata 2

18

Disse inndataene oppfyller begrensningene i deloppgavene $2, 3, 5$.

Eksempel på inndata 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

Eksempel på utdata 3

25

Disse inndataene oppfyller begrensningene i deloppgavene $2, 3, 4, 5$.