Aliruudukot

• Time limit: 1.00 s
• Memory limit: 512 MB

Sinulle annetaan $n \times m$ -ruudukko, jonka jokaisella ruudulla on väri.

Tehtäväsi on etsiä pinta-alaltaan suurin aliruudukko, jolla on seuraava ominaisuus: kaikilla poluilla aliruudukon vasemmasta yläkulmasta oikeaan alakulmaan, joissa kuljetaan vain oikealle tai alas, on samat värit täsmälleen samassa järjestyksessä.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$.

Seuraavat $n$ riviä kuvaavat ruudukon. Jokaisella rivillä on $m$ merkkiä väliltä A–Z, jotka kuvaavat värit.

Tuloste

Tulosta yksi kokonaisluku: suurimman kelvollisen aliruudukon pinta-ala.

Esimerkki

Syöte:
3 5
AABAC
ABACA
ABCAA

Tuloste:
10

Osatehtävä 1 (29 pistettä)

• $1\le n, m\le 10$
  

Osatehtävä 2 (34 pistettä)

• $1\le n, m\le 100$
  

Osatehtävä 3 (37 pistettä)

• $1\le n, m\le 1000$