Перший етап

Limits: 2 sec., 512 MiB

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

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

• Команди, які потрапили у топ \(m\) команд загальної таблиці, проте не більше ніж k команд з одного університету;

• Хоча б одна команда з кожного регіону, навіть якщо вона не потрапила у топ \(m\).

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

Input

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

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

Output

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

Constraints

\(1 \le n \le 1000\),

\(1 \le m \le 200\),

\(1 \le k \le 5\).

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 1 KNU_0_GB_RAM Kyiv KNU LNU_Stallions Lviv LNU KhNURE_KIVI Kharkiv KhNURE KNU_Banderolki Kyiv KNU UzhNU_Machata Zakarpattia UzhNU LNU_Zenyk47_Beer Lviv LNU UzhNU_TroubleMakers Zakarpattia UzhNU	4

Input (stdin) сopy	Output (stdout) сopy
7 4 2 team1 region university team2 region university team3 region university team4 region university team5 region university team6 region university team7 region university	2

Input (stdin) сopy	Output (stdout) сopy
7 4 2 team1 region university1 team2 region university2 team3 region university3 team4 region university4 team5 region university5 team6 region university6 team7 region university7	4

Input (stdin) сopy	Output (stdout) сopy
7 4 2 team1 region1 university1 team2 region2 university2 team3 region3 university3 team4 region4 university4 team5 region5 university5 team6 region6 university6 team7 region7 university7	7

Input (stdin) сopy	Output (stdout) сopy
2 7 4 team1 region1 university1 team2 region2 university2	2

Notes

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

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

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

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