Олимпиады для начинающих: Всероссийская олимпиада по информатике для школьников 5-8 классов имени Келдыша, 2020 год

Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .

На планете Кирнес есть железнодорожный вокзал, с которого проложен железнодорожный путь до Сириуса. Этот путь активно используется товарными поездами, ходящими по одному и тому же ежедневному расписанию с одинаковой скоростью. К началу туристического сезона было решено запустить межпланетные электрички, следующие от вокзала до Сириуса. Электрички ходят по особому расписанию, которое надо согласовать с товарными поездами, поскольку железнодорожный путь является одноколейным.

Каждый день на планете Кирнес состоит из \(h\) часов. Каждый час состоит из \(m\) минут, причём \(m\) обязательно чётное. Известно, что на данный момент \(n\) товарных поездов отправляются с вокзала ежедневно по разу в день: \(i\)-й поезд отправляется в \(h_i\) часов и \(m_i\) минут.

Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны \(\frac{m}{2}\) минутам. То есть для любой электрички предыдущая должна была отправиться ровно за \(\frac{m}{2}\) минут до неё, а следующая должна отправиться ровно через \(\frac{m}{2}\) минут после. Кроме этого, электричку надо подать на платформу за \(k\) минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.

Поскольку электрички отправляются каждый день с интервалом в \(\frac{m}{2}\) минут, то первая электричка отправится с вокзала в 0 часов и \(t\) минут, причем \(t < \frac{m}{2}\). Обратите внимание, что если \(t < k\), то платформа вокзала будет занята и последние \(k - t\) минут предыдущего дня.

Разумеется, не всегда можно составить корректное расписание электричек вместе со всеми товарными поездами. Тогда необходимо отменить некоторые товарные поезда, чтобы появилась возможность пустить электрички с соблюдением всех транспортных норм. При этом, чтобы грузоперевозчики не несли большие убытки, требуется отменить как можно меньше товарных поездов. Составление такого расписания оказалось трудной задачей для правительства планеты, поэтому это было поручено вам. Найдите такое время \(t\) для запуска первой электрички, чтобы количество товарных поездов, которые потребуется отменить, было минимальным.