Shooting King

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

Balloon $i$ starts at height $H_i$ and rises by $S_i$ per second. One balloon can be shot at each integer time $0,1,2,\ldots$. Shooting balloon $i$ at time $t$ incurs penalty $H_i+S_it$. Minimize the maximum penalty.

Input

The first line contains $N$. Each of the next $N$ lines contains $H_i,S_i$.

Output

Print the minimum possible score.

Subtasks

• Subtask 1 — 20%: $N\le50$, $H_i\le10^5$, $S_i\le2000$.
• Subtask 2 — 30%: $N\le5000$.
• Subtask 3 — 50%: $N\le10^5$, $H_i,S_i\le10^9$.

Example

Input

4
5 6
12 4
14 7
21 2

Output

23

Explanation

Shooting in order 3,4,2,1 gives maximum penalty 23.