Mock CCC '22 2 S2 - Kaguya Wants to Grow the Student Council

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 0.25s
Memory limit: 1G

Problem type

It's time to elect a new student council!

There are K candidates who want to join the student council. Each of the N students submits a ballot containing a permutation of the given K candidates. Kaguya wants the council to be as large as possible so that she can spend less time doing administrative work and more time getting Miyuki to confess his love for her. However, because the council positions are ranked, Kaguya cannot simply put every candidate on the student council. In particular, if Kaguya puts candidate i and candidate j on the council, with candidate i ranked higher on the council than candidate j, then every student who submitted a ballot must have ranked candidate i higher than candidate j.

Compute the maximum possible size of the council Kaguya can generate.

Constraints

1 \le N \le 10^4

1 \le K \le 26

In tests worth 1 mark, K \le 2.

In tests worth an additional 4 marks, K \le 8.

Input Specification

The first line contains two integers, N and K.

Each of the next N lines contains a string of length K, consisting of a permutation of the first K uppercase letters.

Output Specification

Output the maximum possible size of the council.

Sample Input 1

2 3
BAC
ABC

Sample Output 1

2

Sample Input 2

3 8
HGBDFCAE
ADBGHFCE
HCFGBDAE

Sample Output 2

3

Sample Input 3

6 8
AHFBGDCE
FABGCEHD
AHDGFBCE
DABHGCFE
ABCHFEDG
DGABHFCE

Sample Output 3

4

Comments

There are no comments at the moment.