Tehtävänanto

JOI-kun leikkii piirto-ohjelmalla.

Piirto-ohjelmassa voi piirtää kuvan suorakulmaiselle ruudukolle, jossa on pystysuunnassa $H$ riviä ja vaakasuunnassa $W$ saraketta. Jokaiselle ruudulle on määritelty väri, ja värit esitetään kokonaislukuina väliltä $1$ ja $10^9$ väliltä.

Ylhäältä lukien $i$-nnellä rivillä ($1 \le i \le H$) ja vasemmalta lukien $j$-nnessä sarakkeessa ($1 \le j \le W$) olevaa ruutua kutsutaan ruuduksi $(i,j)$. Tällä hetkellä ruudun $(i,j)$ väri on $A_{i,j}$.

Niiden ruutujen joukkoa, joihin ruudusta $(i,j)$ voidaan päästä siirtymällä toistuvasti sivustaan viereiseen ruutuun astumatta kertaakaan ruutuun, jonka väri poikkeaa ruudun $(i,j)$ väristä, kutsutaan tässä ruudun $(i,j)$ alueeksi.

Piirto-ohjelmassa on toiminto nimeltä täyttö. Tässä toiminnossa, kun annetaan jokin ruutu $(x,y)$ ($1 \le x \le H$, $1 \le y \le W$) ja väri $c$ ($1 \le c \le 10^9$), kaikkien ruudun $(x,y)$ alueeseen kuuluvien ruutujen väriksi muuttuu $c$.

JOI-kun valitsee jonkin ruudun $(x,y)$ ja värin $c$, ja käyttää täyttöä antaen kyseisen ruudun ja värin täsmälleen $1$ kerran. Täytön käyttämisen jälkeen ruudun $(x,y)$ alueeseen kuuluvien ruutujen lukumäärä on JOI-kunin pistemäärä.

Kirjoita ohjelma, joka etsii suurimman mahdollisen pistemäärän, jonka JOI-kun voi saavuttaa.

Syöte

Syöte annetaan seuraavassa muodossa:

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}

Tuloste

Tulosta $1$ riville suurin mahdollinen pistemäärä, jonka JOI-kun voi saavuttaa.

Rajoitukset

• $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$).
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($9$ pistettä) $H = 1$.
2. ($32$ pistettä) $H \le 30$, $W \le 30$, $A_{i,j} \le 5$ ($1 \le i \le H$, $1 \le j \le W$).
3. ($18$ pistettä) $H \le 30$, $W \le 30$.
4. ($10$ pistettä) $A_{i,j} \le 2$ ($1 \le i \le H$, $1 \le j \le W$).
5. ($31$ pistettä) Ei lisärajoituksia.

Esimerkit

Esimerkkisyöte 1

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

Esimerkkituloste 1

9

Aluksi ruudun $(2,2)$ alueeseen kuuluu $4$ ruutua, jotka ovat ruudut $(1,2), (2,1), (2,2), (3,2)$. Näin ollen, jos täyttöä käytetään antaen ruutu $(2,2)$ ja väri $3$, näiden $4$ ruudun väri muuttuu väriksi $3$ alla olevan kuvan mukaisesti.

Täytön käyttämisen jälkeen ruudun $(2,2)$ alueeseen kuuluu $9$ ruutua, jotka ovat ruudut $(1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2)$. Siispä JOI-kunin pistemääräksi tulee $9$.

Koska JOI-kunin pistemäärää ei ole mahdollista saada vähintään luvuksi $10$, tulostetaan $9$.

Tämä syöte täyttää osatehtävien $2, 3, 5$ rajoitukset.

Esimerkkisyöte 2

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

Esimerkkituloste 2

18

Tämä syöte täyttää osatehtävien $2, 3, 5$ rajoitukset.

Esimerkkisyöte 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

Esimerkkituloste 3

25

Tämä syöte täyttää osatehtävien $2, 3, 4, 5$ rajoitukset.