Vua bắn súng (Shooting King)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ quả bóng. Bóng $i$ ở độ cao ban đầu $H_i$ và mỗi giây tăng thêm $S_i$.

Bạn bắn được đúng một quả tại thời điểm $0$, sau đó tại mỗi thời điểm nguyên $1,2,3,\ldots$ có thể bắn thêm một quả. Thứ tự bắn tùy ý.

Nếu bóng $i$ bị bắn tại thời điểm $t$, điểm phạt của nó là

Điểm của bạn là điểm phạt lớn nhất trong tất cả các bóng. Hãy tìm điểm nhỏ nhất có thể đạt được.

Input

Dòng đầu chứa $N$. $N$ dòng tiếp theo, dòng $i$ chứa $H_i,S_i$.

Output

In điểm nhỏ nhất có thể.

Subtask

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

Ví dụ

Input

4
5 6
12 4
14 7
21 2

Output

23

Giải thích

Có thể bắn các bóng theo thứ tự $3,4,2,1$ tại thời điểm $0,1,2,3$, cho các điểm $14,23,20,23$. Giá trị lớn nhất là $23$ và đây là tối ưu.