В парке развлечений есть K аттракционов. Все аттракционы пронумерованы, начиная с 1. Известно время, в которое каждый посетитель хочет начать свою поездку на аттракционе, и в какое время он закончит кататься на нём. Аттракцион считается свободным, если на нём никто не катается. Каждый посетитель должен выбрать свободный аттракцион с наименьшим номером. Если в момент прихода посетителя все аттракционы заняты, то посетитель уходит, не дожидаясь освобождения одной из них. Если некоторые посетители придут в парк одновременно, они будут кататься на одном и том же аттракционе вместе. Для того, чтобы остановить и запустить аттракцион заново, необходима 1 минута. Со следующей минуты следующие посетители могут воспользоваться аттракционом. Каждый посетитель за весь день может покататься только на одном аттракционе.
Определите, наибольшее количество посетителей, которые придут в парк и покатаются на аттракционах за 24 часа и номер аттракциона, на котором прокатится последний посетитель.
Входные данные. В первой строке входного файла находится два числа K – количество аттракционов в парке развлечений и N – количество посетителей, которые придут в этот парк (натуральные числа, не превышающее 2000). В следующих N строках находятся два значения: минута прихода и минута, не раньше которой посетитель закончит кататься на аттракционе, отсчёт ведётся от начала суток (все числа неотрицательные, не превышающие 1440), для каждого посетителя – в отдельной строке.
Запишите в ответе два целых числа через пробел: сначала количество посетителей, которое сможет воспользоваться аттракционами в парке развлечений за 24 часа, затем номер аттракциона, на котором прокатится последний посетитель.
f = open(’26_11__1vn9j.txt’)
k, n = map(int,f.readline().split())
a = sorted([list(map(int, i.split())) for i in f])
# переменная для подсчета количества человек
count = 0
lt = 0
# переменная которая хранит время запуска определенного атракциона
d_s = [-1]*k
# переменная которая хранит время остановки определенного атракциона
d_e = [-1]*k
# цикл по людям
for x in a:
start,end = x
# цикл по аттракционам
for j in range(k):
# если время запуска больше времени останова прошлого раза
# или если время запуска равно, так как 2 (и более) человека могут кататься на одном аттракционе одновременно
if start > d_e[j] or (start == d_s[j]):
# прибавляем колчество прокатившихся, обновляем переменные конца и начала
count+=1
d_s[j] = start
d_e[j] = end
lt = j+1
# останавливаем цикл, так как для этого человека уже найден аттракцион
break
print(count,lt)