Проходной балл

Problem description

There are a lot of programming competitions around the world. One of the most serious of them has two tours - regional and final. According to rules next students are invited to the final tour:

1. Last year winners are invited to the final tour regardless of this year result on the regional tour;
2. All students whose score is not less than passing score are invited to final tour;
3. If there isn't any student from some region who passed according to first and second rules, then the student whose score in regional tour is biggest in his region is invited to final tour (if there is any participant from this region at all);
4. Only M students at most can be invited to final tour.

We know that all students have different scores on regional tour. Help jury in finding passing score so that all rules are satisfied from the information about regional tour.

Input

On the first line there are 3 integers N (number of participants), M (maximum number of participants can be invited), R (number of different regions which could come to the olympiad), where 1<= M < N. On next N lines there are results of every participant. On each line there are 4 integers: id - unique number of student (1 <= id <= N), region - identifier of region of student (1 <= region <= R), score - participant's score on regional tour (0 <= score <= 10⁹), last number indicates whether participant was winner last year (value is 1) or not (value is 0). We know that there is always a way to satisfy all rules. 1 <= R <= M < N <= 100000.

Output

Write calculated value of M.

Example