Gwailnori

Jaehun loves watching movies on Gwailnori. One day, however, Hakinbot appeared. It is a bot built by the cyber safety guard Byeonghui, and it started blocking access to Gwailnori. Hakinbot appears at regular intervals on the paths that traffic travels through and detects intruders for a few seconds at a time. Jaehun badly wants to watch a movie, so he tries to reach Gwailnori while avoiding Hakinbot.

Consider the following example.

In the example, Jaehun must pass through 4 segments in order to reach Gwailnori. The label A/B on a segment means that the Hakinbot on that segment detects intruders for B seconds, disappears, rests for A seconds, and repeats. In other words, the bot appears at intervals of A seconds, and each time it appears it stays active for B seconds. At the moment an intruder appears (time 0), the bots on all segments appear at once and start their activity.

Jaehun has to move while hiding in the network devices along the route. When he is at the start of a segment and the bot of that segment is active, he cannot enter the segment and must wait until the bot disappears. While the bot is resting, he can leave immediately. Passing through one segment takes 1 second.

Here is the example step by step.

• At Jaehun's phone (time 0): the bot has just appeared, so he waits 5 seconds and then moves to the next segment.
• At the first switch (time 6): the bot is resting, so he moves on immediately without waiting.
• At the second router (time 7): the bot has 2 seconds of activity left, so he waits 2 seconds and then moves on.
• At the third server (time 10): the bot has 4 seconds of activity left, so he waits 4 seconds and then moves on.

So in the example, Jaehun needs at least 15 seconds to reach Gwailnori.

The mischievous hacker Junoh Lim (a resident of Dongtan) wants to report Jaehun to the police and teach him some ethics. While Junoh is dialing 112, the police emergency number, find Jaehun's minimum access time and tell it to Junoh.

The first line contains $N$, the number of segments Jaehun must pass through ($1 \le N \le 50{,}000$).

Each of the next $N$ lines contains two integers $a$ and $b$ separated by a space, describing the bot on the $i$-th segment. This bot appears at intervals of $a$ seconds, and each time it appears it stays active for $b$ seconds and then disappears ($1 \le a, b \le 1{,}000$).

Print the minimum time, in seconds, Jaehun needs to reach Gwailnori.