Обработка данных с сортировкой

(М. Коктышев) В аквапарке посетители могут оставлять вещи в камерах хранения. Камеры хранения бывают двух типов: обычные и холодильные. Обычная камера обозначается цифрой 0, холодильная - цифрой 1. Все камеры пронумерованы натуральными числами начиная с 1.

Для каждой камеры известны её тип и объём. Посетитель может воспользоваться камерой хранения, если тип камеры совпадает с требуемым типом заявки, а объём камеры не меньше объёма его багажа.

В течение суток посетители отправляют заявки на использование камер хранения. В каждой заявке указаны время начала хранения, время окончания хранения, необходимый объём камеры и требуемый тип камеры. Перед обработкой все заявки упорядочиваются по возрастанию времени начала, а при одинаковом времени начала - по возрастанию времени окончания. Если время начала и время окончания у нескольких заявок совпадают, они обрабатываются в том порядке, в котором записаны во входном файле.

Для каждой заявки администратор выбирает свободную подходящую камеру минимального объёма. Если таких камер несколько, выбирается камера с наименьшим номером. Камера считается свободной для нового посетителя только начиная со следующей минуты после окончания предыдущего хранения. Если в момент обработки заявки подходящей свободной камеры нет, посетитель уходит.

Определите, сколько посетителей смогут воспользоваться камерами хранения в течение суток, и номер камеры, которая будет выдана посетителю последней. Если несколько камер были выданы в самое позднее время, укажите наименьший номер такой камеры.

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

В первой строке входного файла находятся два натуральных числа K и N: K - количество камер хранения, N - количество заявок посетителей. Значения K и N не превышают 10 000.

В следующих K строках находятся по два числа: тип камеры и её объём. Объём камеры - натуральное число, не превышающее 100 000.

В следующих N строках находятся по четыре числа: время начала хранения, время окончания хранения, необходимый объём камеры и требуемый тип камеры. Время указывается в минутах от начала суток и не превышает 1440. Необходимый объём камеры не превышает 100 000.

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

Запишите в ответе два натуральных числа: сначала количество посетителей, которые смогут воспользоваться камерами хранения, затем номер камеры, которая будет выдана посетителю последней.

Типовой пример организации данных во входном файле

4 9 0 50 1 60 0 100 1 120 20 40 55 0 10 30 45 0 31 50 55 1 15 25 60 1 41 70 90 0 26 35 50 0 51 80 100 1 36 60 110 1 71 90 40 0

При таких исходных данных камеры хранения смогут получить 7 посетителей. Заявка с временем начала 26 не будет выполнена, так как в этот момент нет свободной обычной камеры подходящего объёма. Заявка с временем начала 51 также не будет выполнена, так как в этот момент нет свободной холодильной камеры подходящего объёма. Последней будет выдана камера №1 для заявки с временем начала 71.

Ответ: 7 1

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.