There is a racetrack where
$n$ players complete laps. Each player
has their own maximum speed. In this racetrack, overtaking is
only possible near the finish line at every lap: when a player
approaches a slower player, she will stay behind him until at
the finish line. At the finish line, all players crossing the
line at the same time resume driving at their maximum speed (so
faster players overtake slower ones). Initially, all players
start at the finish line. Given the lap time and the number of
laps to complete for each player, calculate the times they
complete the race in.
Input
The first line contains an integer $n$ ($1
\leq n \leq 5\, 000$), the number of players. The
following $n$ lines
contain the players’ lap time and number of laps to complete:
the $i$th line contains
two integers $t_ i$ and
$c_ i$ ($1 \leq t_ i \leq 10^6$, $1 \leq c_ i \leq 1\, 000$), the lap
time and the number of laps to complete for player $i$. The players are sorted in
decreasing order of speed, that is, $t_1 \leq t_2 \leq \ldots \leq t_
n$.
Output
Output $n$ lines; the
$i$’th line must contain
the time that player $i$
completes the race.
Sample Input 1 
Sample Output 1 
2
4 8
7 6

36
42
