Énoncé

JOI-kun joue avec un logiciel de dessin.

Dans ce logiciel de dessin, on peut dessiner sur une grille rectangulaire de $H$ lignes verticalement et $W$ colonnes horizontalement. Chaque case possède une couleur déterminée, et les couleurs sont représentées par des entiers compris entre $1$ et $10^9$ inclus.

La case située à la $i$-ème ligne depuis le haut ($1 \le i \le H$) et à la $j$-ème colonne depuis la gauche ($1 \le j \le W$) est appelée case $(i,j)$. Actuellement, la couleur de la case $(i,j)$ est $A_{i,j}$.

L'ensemble des cases accessibles depuis la case $(i,j)$ en se déplaçant de manière répétée vers une case adjacente par un côté, sans jamais entrer dans une case d'une couleur différente de celle de la case $(i,j)$, est appelé ici la région de la case $(i,j)$.

Le logiciel de dessin dispose d'une fonctionnalité appelée remplissage. Avec cette fonctionnalité, lorsqu'on spécifie une certaine case $(x,y)$ ($1 \le x \le H$, $1 \le y \le W$) et une couleur $c$ ($1 \le c \le 10^9$), la couleur de toutes les cases contenues dans la région de la case $(x,y)$ devient $c$.

JOI-kun choisit une certaine case $(x,y)$ et une couleur $c$, et utilise le remplissage en spécifiant cette case et cette couleur exactement $1$ fois. Le nombre de cases contenues dans la région de la case $(x,y)$ après avoir utilisé le remplissage sera le score de JOI-kun.

Écrivez un programme permettant de trouver le score maximal que JOI-kun peut obtenir.

Entrée

L'entrée est donnée dans le format suivant :

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}

Sortie

Affichez sur $1$ ligne le score maximal que JOI-kun peut obtenir.

Contraintes

• $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$).
• Toutes les valeurs d'entrée sont des entiers.

Sous-tâches

1. ($9$ points) $H = 1$.
2. ($32$ points) $H \le 30$, $W \le 30$, $A_{i,j} \le 5$ ($1 \le i \le H$, $1 \le j \le W$).
3. ($18$ points) $H \le 30$, $W \le 30$.
4. ($10$ points) $A_{i,j} \le 2$ ($1 \le i \le H$, $1 \le j \le W$).
5. ($31$ points) Aucune contrainte supplémentaire.

Exemples

Exemple d'entrée 1

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

Exemple de sortie 1

9

Initialement, la région de la case $(2,2)$ contient $4$ cases : les cases $(1,2), (2,1), (2,2), (3,2)$. Par conséquent, si l'on utilise le remplissage en spécifiant la case $(2,2)$ et la couleur $3$, la couleur de ces $4$ cases devient $3$, comme illustré dans la figure ci-dessous.

Après avoir utilisé le remplissage, la région de la case $(2,2)$ contient $9$ cases : les cases $(1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2)$. Ainsi, le score de JOI-kun est de $9$.

Comme le score de JOI-kun ne peut pas être supérieur ou égal à $10$, on affiche $9$.

Cette entrée satisfait les contraintes des sous-tâches $2, 3, 5$.

Exemple d'entrée 2

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

Exemple de sortie 2

18

Cette entrée satisfait les contraintes des sous-tâches $2, 3, 5$.

Exemple d'entrée 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

Exemple de sortie 3

25

Cette entrée satisfait les contraintes des sous-tâches $2, 3, 4, 5$.