Hide

Problem H
Longest Common Subsequence

You are given $n$ strings, each a permutation of the first $k$ upper-case letters of the alphabet.

String $s$ is a subsequence of string $t$ if and only if it is possible to delete some (possibly zero) characters from the string $t$ to get the string $s$.

Compute the length of the longest common subsequence of all $n$ strings.

Input

The first line of input contains two integers $n$ ($1 \le n \le 10^5$) and $k$ ($1 \le k \le 26$), where $n$ is the number of strings, and the strings are all permutations of the first $k$ upper-case letters of the alphabet.

Each of the next $n$ lines contains a single string $t$. It is guaranteed that every $t$ contains each of the first $k$ upper-case letters of the alphabet exactly once.

Output

Output a single integer, the length of the longest subsequence that appears in all $n$ strings.

Sample Input 1 Sample Output 1
2 3
BAC
ABC
2
Sample Input 2 Sample Output 2
3 8
HGBDFCAE
ADBGHFCE
HCFGBDAE
3
Sample Input 3 Sample Output 3
6 8
AHFBGDCE
FABGCEHD
AHDGFBCE
DABHGCFE
ABCHFEDG
DGABHFCE
4
CPU Time limit 1 second
Memory limit 2048 MB
Statistics Show
Source 2020 ICPC North America Regionals (March 6 2021)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in