5. Семейный телепросмотр

В многодетной семье Морозовых постоянно в новогоднюю ночь возникают конфликты по поводу выбора телеканала для просмотра за праздничным столом. После того, как 1 января 2021 в ходе 11 микродрак за пульт от телевизора произошло 2 макания вышеупомянутого пульта в оливье, 3 погружения в селёдку под шубой и одно фатальное падение пульта на пол (умная кошка Муся быстренько укатила под диван выпавшую из развалившегося пульта батарейку), было принято решение в следующий Новый год планировать просмотр заранее.

Была вывешена на стенку программа всех доступных телеканалов, и все члены семьи поставили галочки у тех телепередач, которые они готовы смотреть за новогодним столом (при этом часто отмечались передачи, идущие одновременно или накладывающиеся по времени). Данные о передачах, заинтересовавших хотя бы одного члена семьи, были записаны в виде строк типа “qqq 00:15 03:25 7”, где первый элемент строки – уникальное название («идентификатор», как сказал Морозов-старший) передачи из букв латиницы, второй и третий – время начала и время окончания передачи (ЧЧ:ММ в интервале от 00:00 до 06:00), четвёртый – количество членов семьи, готовых смотреть данную передачу). Затем был составлен план переключения каналов, обеспечивающий максимальное возможное суммарное количество минут просмотра членами семьи желаемых передач. Согласно этому плану, переключения можно было выполнять в любой момент, не дожидаясь окончания текущей телепередачи.

Вот это самое максимальное возможное суммарное количество человекоминут телеудовлетворения и должна вычислить ваша программа.

Входные данные. В первой строке натуральное число N – количество описанных телепередач. Далее следуют N строк описанной выше структуры. Значение N и количество членов семьи – в пределах разумного и реального.

Выходные данные. Одно натуральное число – максимальная сумма количеств минут, во время которых член семьи смотрит желаемые передачи, по всем членам семьи Морозовых.

Пример: при вводе вот таких данных
5
qqq 00:15 02:30 2
www 00:30 01:45 4
eee 03:00 06:00 1
rrr 04:20 05:30 3
sss 02:00 03:40 2
программа должна вывести 840.