Descrizione

JOI-kun sta giocando con un programma di disegno.

Nel programma di disegno è possibile disegnare su una griglia rettangolare di $H$ righe in verticale e $W$ colonne in orizzontale. A ciascuna cella è assegnato un colore, e i colori sono rappresentati da numeri interi compresi tra $1$ e $10^9$ inclusi.

La cella situata nella $i$-esima riga dall'alto ($1 \le i \le H$) e nella $j$-esima colonna da sinistra ($1 \le j \le W$) è chiamata cella $(i,j)$. Attualmente, il colore della cella $(i,j)$ è $A_{i,j}$.

L'insieme delle celle raggiungibili dalla cella $(i,j)$ spostandosi ripetutamente in una cella adiacente per lato senza mai entrare in una cella di colore diverso da quello della cella $(i,j)$ è chiamato qui la regione della cella $(i,j)$.

Il programma di disegno dispone di una funzione chiamata riempimento. Con questa funzione, quando si specificano una certa cella $(x,y)$ ($1 \le x \le H$, $1 \le y \le W$) e un colore $c$ ($1 \le c \le 10^9$), il colore di tutte le celle contenute nella regione della cella $(x,y)$ diventa $c$.

JOI-kun sceglie una certa cella $(x,y)$ e un colore $c$, e utilizza il riempimento specificando quella cella e quel colore esattamente $1$ volta. Il numero di celle contenute nella regione della cella $(x,y)$ dopo aver usato il riempimento sarà il punteggio di JOI-kun.

Scrivi un programma per trovare il punteggio massimo ottenibile da JOI-kun.

Input

L'input è fornito nel seguente formato:

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}

Output

Stampa su $1$ riga il punteggio massimo ottenibile da JOI-kun.

Vincoli

• $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$).
• Tutti i valori di input sono interi.

Sottoproblemi

1. ($9$ punti) $H = 1$.
2. ($32$ punti) $H \le 30$, $W \le 30$, $A_{i,j} \le 5$ ($1 \le i \le H$, $1 \le j \le W$).
3. ($18$ punti) $H \le 30$, $W \le 30$.
4. ($10$ punti) $A_{i,j} \le 2$ ($1 \le i \le H$, $1 \le j \le W$).
5. ($31$ punti) Nessun vincolo aggiuntivo.

Esempi

Esempio di input 1

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

Esempio di output 1

9

All'inizio, le celle contenute nella regione della cella $(2,2)$ sono $4$, ovvero le celle $(1,2), (2,1), (2,2), (3,2)$. Pertanto, se si usa il riempimento specificando la cella $(2,2)$ e il colore $3$, il colore di queste $4$ celle diventa $3$, come mostrato nella figura sottostante.

Dopo aver usato il riempimento, le celle contenute nella regione della cella $(2,2)$ diventano $9$, ovvero le celle $(1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2)$. Pertanto, il punteggio di JOI-kun diventa $9$.

Poiché non è possibile fare in modo che il punteggio di JOI-kun sia $10$ o più, si stampa $9$.

Questo input soddisfa i vincoli dei sottoproblemi $2, 3, 5$.

Esempio di input 2

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

Esempio di output 2

18

Questo input soddisfa i vincoli dei sottoproblemi $2, 3, 5$.

Esempio di input 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

Esempio di output 3

25

Questo input soddisfa i vincoli dei sottoproblemi $2, 3, 4, 5$.