Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит.
Входные данные представлены в файле следующим образом.
В первой строке входного файла находится натуральное число 
, не превышающее 1000, – количество ячеек в камере хранения. Во второй строке – натуральное число 
(
1000), обозначающее количество пассажиров. Каждая из следующих 
строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).
Требуется выбрать для каждой ячейки один багаж, который находился в ней в течении 24 часов так, чтобы сумма времени хранения всех выбранных багажей была максимальной и не кратной 13.
В ответе запишите одно число: найденное произведение.
Пример входного файла:
2
5
30 60
40 1000
59 60
61 1000
1010 1440
f = open(’26-2.txt’)
k = int(f.readline()) # Kоличество ячеек
n = int(f.readline()) # Kоличество пассажиров
# Сортировка пассажиров по времени сдачи багажа
a = sorted([list(map(int, i.split())) for i in f])
cell = [[] for i in range(k)] # Cписок ячеек
for i in a: # Для каждой заявки пассажира
for j in range(k): # Ищем свободную ячейку
# Если ячейка пустая или успеет освободиться
if (not cell[j]) or (i[0] > cell[j][-1][1]):
cell[j].append(i) # Добавляем заявку в ячейку
break # Останавливаем поиск
# Вычисляем длительность каждого хранения багажа в ячейках
t = [[j[1]-j[0] for j in i] for i in cell]
s = 0 # Сумма всех длительностей
mr = 1000050000 # Минимальная разница
for i in t: # Проходим по каждой ячейке
line = sorted(i, reverse=True) # Сортировка длительностей по убыванию
s += line[0] # Добавление максимальной длительности к общей сумме
if len(line) > 1: # Если в ячейке больше одной длительности
for j in range(1, len(line)): # Ищем минимальную разницу не кратную 13
if (line[0]-line[j] < mr) and ((line[0]-line[j]) % 13 !=0):
mr = line[0]-line[j] # Обновляем минимальную разницу
if s % 13 == 0:
s = s - mr
print(s)