У першому етапі одного цілком вигаданого змагання беруть участь команд. Та, на жаль, правила проходу у другий етап занадто заплутані, тож допоможіть організаторам визначити, скільки ж команд потрапить у другий етап.
У другий етап проходять:
Команди, які потрапили у топ команд загальної таблиці, проте не більше ніж k команд з одного університету;
Хоча б одна команда з кожного регіону, навіть якщо вона не потрапила у топ .
Дано результати першого етапу у порядку від найкращої до найгіршої команди. Визначте, скільки команд потрапить у другий етап. Жодні 2 чи більше команди не можуть ділити те ж місце.
В першому рядку задано 3 числа , та – кількість команд, топ команд, які проходять у другий етап, та максимальна кількість команд з одного університету.
В наступних рядках задано по 3 рядки розділених пробілами – назва команди, назва регіону та назва університету. Команди задані в порядку від першої до останньої.
1 \le n \le 1000,
1 \le m \le 200,
1 \le k \le 5.
Усі назви складаються з великих чи маленьких латинських букв, цифр чи символу _ довжиною до 20 символів. Назви є різними, якщо відрізняються хоча б одним символом, маленькі та великі букви вважаємо різними.
Усі назви команд різні, команди з одного університету також представляють один регіон.
Виведіть єдине число – кількість команд, які потраплять у другий етап.
Приклад
Приклад 1
Приклад 2
Приклад 3
Приклад 4
У першому прикладі у другий етап проходять команди KNU_0_GB_RAM, LNU_Stallions, KhNURE_KIVI та UzhNU_Machata. Команда KNU_Banderolki не пройшла, адже вона зайняла 2 місце серед команд університету KNU. Команда UzhNU_Machata пройшла, адже вона зайняла перше місце серед команд регіону Zakarpattia.
У другому прикладі всі команди з одного університету, отже у другий етап проходять k=2 команди.
У третьому прикладі усі команди з одного регіону, але з різних університетів, отже у другий етап проходять m=4 команд.
У четвертому всі команди з різних регіонів, отже вони усі проходять у другий етап.