**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше значения по умолчанию.**
Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные
станции \(A\) и \(B\). В связи с ограничением бюджета, эти станции соединены только
одной дорогой. Если поезд отправляется от одной станции в момент времени \(t\),
тогда он прибудет на другую станцию в момент времени \(t+T\) (\(1\le T\le 10^{12}\)).
Имеется \(N\) (\(1\le N\le 5000\)) поездов для которых нужно установить время отправки.
\(i\)-ый поезд должен покинуть станцию \(s_i\) в момент времени $ti или позже
(\(s_i\in \{A, B\}, 0\le t_i\le 10^{12}\)).
Запрещено иметь поезда, которые движутся в противоположных направлениях в
один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь
множество поездов, которые еду в одном направлении в одно и то же время
(предполагаем, что поезда имеют пренебрежимо малые размеры)
Помогите Беси спланрировать времена отправления так, чтобы не было столкновений,
а общая задержка была минимальной. Если поезд спланирован на убытие
в момент времени \(a_i\ge t_i\), общая задержка определяется как \(\sum_{i=1}^N(a_i-t_i)\).
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит
\(N\) и
\(T\).
Затем следуют \(N\) строк, где i-ая строка содержит станции \(s_i\) и время \(t_i\),
соответствующие \(i\)-ому поезду.
ФОРМАТ ВЫВОДА (на экран):
Минимально возможная общая задержка всех корректных планирований.
Ваш ответ: