Problem Description

Takahashi has recently become obsessed with shooting.

Takahashi is participating in a competition where he aims to pop all $ N $ balloons with a shooting game, trying to minimize the score he receives.

The balloons are numbered from $ 1 $ to $ N $. Balloon $i\ (1\ ≦\ i\ ≦\ N)$ is initially at height $ H_i $ and increases its height by $ S_i $ each second.

Takahashi can pop one balloon at the start of the competition and can pop one balloon per second thereafter. The order in which he pops the balloons is decided by Takahashi.

For each balloon, a penalty is incurred when it is popped. The penalty is equal to the height of the balloon at the time it is popped. Takahashi's final score is the maximum penalty among the $ N $ balloons.

Determine the minimum score Takahashi can achieve.

Input Format

The input is given from the standard input in the following format:

$ N $ $ H_1 $ $ S_1 $ $ H_2 $ $ S_2 $ : $ H_N $ $ S_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 100,000)$, representing the number of balloons.
• The next $ N $ lines provide information about the balloons. The $i\ (1\ ≦\ i\ ≦\ N)$th line contains two integers $H_i\ (1\ ≦\ H_i\ ≦\ 1,000,000,000)$ and $S_i\ (1\ ≦\ S_i\ ≦\ 1,000,000,000)$ separated by a space. These indicate that balloon $ i $ is initially at height $ H_i $ and increases its height by $ S_i $ each second.

Output Format

Output the minimum score Takahashi can achieve on a single line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
5 6
12 4
14 7
21 2

Sample Output #1

23

Sample Input #2

6
100 1
100 1
100 1
100 1
100 1
1 30

Sample Output #2

105

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N\ ≦\ 50$ and $H_i\ ≦\ 100,000$ and $S_i\ ≦\ 2,000$, you will be awarded $ 30 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 70 $ points.

Sample Explanation 1

For example, pop the balloons in the following order:
- Immediately pop balloon $ 3 $. The penalty for balloon $ 3 $ is $14\ +\ 7\ ×\ 0\ =\ 14$.
- After $ 1 $ second, pop balloon $ 4 $. The penalty for balloon $ 4 $ is $21\ +\ 2\ ×\ 1\ =\ 23$.
- After $ 2 $ seconds, pop balloon $ 2 $. The penalty for balloon $ 2 $ is $12\ +\ 4\ ×\ 2\ =\ 20$.
- After $ 3 $ seconds, pop balloon $ 1 $. The penalty for balloon $ 1 $ is $5\ +\ 6\ ×\ 3\ =\ 23$.
Thus, Takahashi's score is $ 23 $, which is the minimum possible.

见题面 Input 部分

见题面 Output 部分