Racetrack

Time limit2sMemory limit512 MB

Summary

Given ordered lap times and lap counts and the rule that passes happen only at the finish line, compute when each runner finishes the race.

Level: Hard8 of 10
Topics: Simulation, Implementation, Sorting, Math
Solved: No attempts yet

Problem

On a circular racetrack, $n$ players run a fixed number of laps. Every player has her own maximum speed. Player $i$ needs $t_i$ units of time for one lap at maximum speed and has to complete $c_i$ laps.

On this track a player can pass another player only at the finish line. When a player catches up with a slower player during a lap, she stays right behind him until the end of that lap, so the two cross the finish line at the same moment.

Every player who crosses the finish line at the same moment starts again from there at her own maximum speed, so faster players move ahead of slower ones.

At the start all players stand together at the finish line. A player who completes her last lap leaves the track at once and blocks nobody after that.

Given the lap time and the number of laps of every player, compute the moment each player completes the race.

Input

The first line contains the number of players $n$ ( $1 \le n \le 5000$ ).

Each of the next $n$ lines describes one player: the $i$ -th of them contains the lap time $t_i$ and the number of laps $c_i$ of player $i$ ( $1 \le t_i \le 10^6$ , $1 \le c_i \le 1000$ ).

The players are given in order of decreasing speed, that is $t_1 \le t_2 \le \dots \le t_n$ .

Output

Print $n$ lines. The $i$ -th line contains the moment player $i$ completes the race.

Examples2

Example 1
Input
```
2
4 8
7 6
```
Expected output
```
36
42
```
Example 2
Input
```
3
1 4
3 3
4 3
```
Expected output
```
8
9
12
```