Cerința

Se dă o matrice de mărime N pe N care conține litere ale alfabetului englez. Definim un drum dreapta-jos ca fiind un șir de celule ale matricei care începe cu celula (1, 1), se termină cu celula (N, N), iar pentru fiecare celulă (x, y) din drum (exceptând ultima), succesoarea sa este fie (x+1, y), fie (x, y+1). Spunem că șirul de caractere generat de un drum în matrice este șirul obținut prin concatenarea valorilor celulelor drumului în ordine.

Să se găsească 2 drumuri dreapta-jos care nu se intersectează (decât în celulele (1, 1) și (N, N)) pentru care coeficientul de similaritate este maxim. Coeficientul de similaritate a 2 drumuri reprezintă numărul de poziții i pentru care a[i] = b[i], 0 ≤ i < lungime(a), lungime(b), unde a și b sunt șirurile generate de cele 2 drumuri.

Date de intrare

Prima linie conține valoarea lui N. Următoarele N linii conțin câte N litere mici ale alfabetului englez, reprezentând matricea.

Date de ieșire

Prima linie va conține coeficientul maxim de similaritate între 2 drumuri dreapta jos care nu se interesectează decât în capete.

Restricții și precizări

• 1 ≤ N ≤ 300

Punctare

• Pentru teste în valoare de 20 de puncte, 1 ≤ N ≤ 7.
• Pentru teste în valoare de 50 de puncte, 1 ≤ N ≤ 50.
• Pentru teste în valoare de 80 de puncte, 1 ≤ N ≤ 150.

Exemplu 1:

douadrumuri.in

3
abe
cef
zfq

douadrumuri.out

4

Exemplu 2:

douadrumuri.in

4
abcd
bcde
aaaa
zdef

douadrumuri.out

5

Explicații

În primul exemplu, drumurile sunt:

• (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3)
• (1, 1) → (2, 1) → (2, 2) → (3, 2) → (3, 3)

Șirurile generate de acestea sunt:

• abefq
• acefq