Перший етап#12954

Перший етап

2 секунди
512 мегабайтів
Середня

У першому етапі одного цілком вигаданого змагання беруть участь команд. Та, на жаль, правила проходу у другий етап занадто заплутані, тож допоможіть організаторам визначити, скільки ж команд потрапить у другий етап.

У другий етап проходять:

Дано результати першого етапу у порядку від найкращої до найгіршої команди. Визначте, скільки команд потрапить у другий етап. Жодні 2 чи більше команди не можуть ділити те ж місце.

Вхідні дані

В першому рядку задано 3 числа , та – кількість команд, топ команд, які проходять у другий етап, та максимальна кількість команд з одного університету.

В наступних рядках задано по 3 рядки розділених пробілами – назва команди, назва регіону та назва університету. Команди задані в порядку від першої до останньої.

1 \le n \le 1000,

1 \le m \le 200,

1 \le k \le 5.

Усі назви складаються з великих чи маленьких латинських букв, цифр чи символу _ довжиною до 20 символів. Назви є різними, якщо відрізняються хоча б одним символом, маленькі та великі букви вважаємо різними.

Усі назви команд різні, команди з одного університету також представляють один регіон.

Вихідні дані

Виведіть єдине число – кількість команд, які потраплять у другий етап.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Приклад 4

Loading
Loading

Примітка

У першому прикладі у другий етап проходять команди KNU_0_GB_RAM, LNU_Stallions, KhNURE_KIVI та UzhNU_Machata. Команда KNU_Banderolki не пройшла, адже вона зайняла 2 місце серед команд університету KNU. Команда UzhNU_Machata пройшла, адже вона зайняла перше місце серед команд регіону Zakarpattia.

У другому прикладі всі команди з одного університету, отже у другий етап проходять k=2 команди.

У третьому прикладі усі команди з одного регіону, але з різних університетів, отже у другий етап проходять m=4 команд.

У четвертому всі команди з різних регіонів, отже вони усі проходять у другий етап.