Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Бег по эскалатору

(Время: 2 сек. Память: 16 Мб Сложность: 33%)

Пусть N человек бегут вниз по эскалатору, причем i-ый пробегает одну ступеньку за ti секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены «обгоны», то есть если человек A в процессе бега догнал человека B, который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B. Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно.

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

Входные данные

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 105). В следующих N строках перечислены пары чисел ti, wi (1 ≤ ti, wi ≤ 106) – время пробега одной ступени и количество ступеней до конца эскалатора для i-го человека. Гарантируется, что изначально всем людям осталось бежать различное число ступеней.

Выходные данные

В i-ой строке выходного файла OUTPUT.TXT выведите время в секундах, через которое i-ый человек сойдет с эскалатора.

Пример

INPUT.TXTOUTPUT.TXT
13
2 10
3 11
1 12
20
33
33

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ