First Stage

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

In the first stage of a completely fictional competition, \(n\) teams participate. Unfortunately, the rules for advancing to the second stage are too confusing, so help the organizers determine how many teams will make it to the second stage.

The following advance to the second stage:

• Teams that made it to the top \(m\) teams of the general standings, but no more than \(k\) teams from the same university;

• At least one team from each region, even if it did not make it to the top \(m\).

Given the results of the first stage in order from best to worst team, determine how many teams will advance to the second stage. No 2 or more teams can share the same place.

Input

The first line contains 3 numbers \(n\), \(m\), and \(k\) – the number of teams, the top teams that advance to the second stage, and the maximum number of teams from a single university.

The next \(n\) lines each contain 3 space-separated strings – the team name, the region name, and the university name. The teams are given in order from the first to the last.

Output

Print a single integer – the number of teams that will advance to the second stage.

Constraints

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

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

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

All names consist of uppercase or lowercase Latin letters, digits, or the _ symbol, up to 20 characters in length. Names are different if they differ by at least one character; lowercase and uppercase letters are considered different.

All team names are unique; teams from the same university also represent the same region.

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

In the first example, the teams that advance to the second stage are KNU_0_GB_RAM, LNU_Stallions, KhNURE_KIVI, and UzhNU_Machata. The team KNU_Banderolki did not advance because it took 2nd place among the teams of the KNU university. The team UzhNU_Machata advanced because it took first place among the teams of the Zakarpattia region.

In the second example, all teams are from the same university, so \(k=2\) teams advance to the second stage.

In the third example, all teams are from the same region, but from different universities, so \(m=4\) teams advance to the second stage.

In the fourth, all teams are from different regions, so they all advance to the second stage.