чемпионаты Спб: Чемпионат СПБ 2013

В одном далеком мире, в славном городе Эрбовле открыли новый банк. В банке есть \(m\) сотрудников, работающих с клиентами, и один главный бухгалтер.

Для решения своих проблем в банк приходят гномы. Известно, что \(i\)-й гном приходит в банк через \(t_i\) минут после открытия банка. Сначала ему нужно провести \(a_i\) минут у одного из \(m\) сотрудников, а потом еще \(b_i\) минут в офисе главного бухгалтера.

Разумеется несколько гномов не могут одновременно находиться у одного сотрудника или в офисе главного бухгалтера, поэтому к сотрудникам и к главному бухгалтеру формируются очереди.

Очередь к сотрудникам общая, при этом гном из очереди идет к первому освободившемуся сотруднику. Если в банк одновременно приходят два гнома, то первым в очередь к сотрудникам встает тот, чей номер меньше. Если гном начал обслуживаться у сотрудника в момент \(x\), то он освобождается в момент \(x+a_i\), в этот момент другой гном может начать обслуживаться у этого же сотрудника. Гном, пришедший в банк в момент \(t\), может начать обслуживаться у сотрудника в любой момент, начиная с \(t\).

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

Сегодня в банк собирается прийти \(n\) гномов, про каждого известно: во сколько он заходит в банк, сколько времени он хочет провести у окошка и сколько времени он хочет провести у бухгалтера. Нужно сообщить время выхода из банка для каждого гнома.