|
Бег по эскалатору
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 3
2 10
3 11
1 12 |
20
33
33 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
