Одна Дуже Престижна Олімпіада, як і всі престижні олімпіади останнім часом, складається з двох турів - регіонального та заключного. Правила відбору до другого туру (заключний етап) прості:

• Призери олімпіади минулого року запрошуються на заключний етап незалежно від набраних ними у першому турі балів.
• Усі учасники, які набрали не менше балів, ніж встановлений журі прохідний бал, проходять до другого туру.
• Якщо в якомусь із регіонів жоден учасник за першими двома правилами у другий тур не пройшов, то на заключний етап запрошується учасник із цього регіону, який набрав у ньому максимальну кількість балів (це не стосується регіонів, від яких учасників не було).
• На другий тур можна запросити не більше \(𝑀\) учасників.

Відомо, що жодні два учасники не набрали однакову кількість балів. За інформацією про результати першого туру, допоможіть журі встановити мінімально можливий прохідний бал, при якому всі правила відбору будуть виконані.

Формат вхідних даних

У першому рядку вхідного файлу містяться три цілих числа \(𝑁\) , \(𝑀\) і \(𝑅\)  - число учасників першого туру, максимально можливе число учасників другого туру та кількість регіонів, з яких могли бути учасники (\(1≤𝑀<𝑁\) ).

Далі в \(N\) рядках містяться результати кожного з учасників. Кожен рядок складається з чотирьох цілих чисел. Спочатку йде \(𝑖𝑑\)  - унікальний ідентифікатор учасника (\(1≤𝑖𝑑≤𝑁 \)), далі номер регіону \(𝑟𝑒𝑔𝑖𝑜𝑛\) , в якому даний учасник навчається (\(1≤ 𝑟𝑒𝑔𝑖𝑜𝑛 \le R\) ), потім \(𝑠𝑐𝑜𝑟𝑒\)  - число балів, набраних учасником, четверте число дорівнює 1, якщо учасник є призером олімпіади минулого року, і 0 - в іншому випадку.

Гарантується, що всі ідентифікатори учасників є різними, жодні два учасники не набрали однакову кількість балів, і виконати всі правила відбору можливо.

Формат вихідних даних

Виведіть одне число - мінімальний прохідний бал, який можна встановити.

Оцінювання

Тести складаються із чотирьох груп. У всіх тестах \(0≤𝑠𝑐𝑜𝑟𝑒≤10^9\) .

• Тест 1 з умови оцінюється в 0 балів.
• У тестах цієї групи всі числа на вході не перевищують 1000. Ця група оцінюється в 30 балів, причому бали нараховуються тільки при проходженні всіх тестів групи.
• У тестах цієї групи \(1≤𝑅≤𝑀≤10000\), \(𝑀<𝑁≤100000\). Ця група також оцінюється у 30 балів, бали нараховуються лише за проходження всіх тестів групи.
• У тестах цієї групи, \(1≤𝑅≤𝑀<𝑁≤100000\) .

Приклад вхідних даних

9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0

Приклад вихідних даних

985