@Pavlin234

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

Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
На второй тур можно пригласить не более M участников.

Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.

Входные данные

В первой строке входного файла содержатся три целых числа N, M и R - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (1MN ). Далее в N строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет id - уникальный идентификатор участника (1idN), далее номер региона region, в котором данный участник учится (1regionR), затем score - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

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

Выходные данные

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

Примечания

Тесты состоят из четырёх групп. Во всех тестах 0score109.

Тест 1 из условия, оценивается в 0 баллов.
В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1RM10000 , MN100000 . Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Offline-группа, 1RMN100000 . Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.

Примеры
Входные данные

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

0

@bormant

Это задание Отборочного тура на Московскую олимпиаду по информатике для 9 классов (2018 г)
Отборочный этап проходит с 11.12.2017 по 11.02.2018 (включительно).

Пункт 4.7 Правил форума, которые вы при регистрации обещали неукоснительно выполнять, гласит:
Как можно более полно описывайте (1) суть проблемы или вопроса, (2) что было сделано для ее решения и (3) какие результаты получены.

0