Ở Vương quốc Kiến, các con kiến xây một con đường hầm dài và thẳng. Mỗi gia đình kiến định cư tại một vị trí trên con đường này, tại đây chúng sống và dự trữ thức ăn để qua mùa đông giá lạnh.

Các con kiến làm việc rất hiệu quả, chúng đã nhặt được nhiều hạt lúa mì cho gia đình của mình. Để động viên cổ vũ các gia đình kiến và đảm bảo tính công bằng, Nữ hoàng Kiến quyết định mỗi gia đình sẽ được đón tiếp K thành viên của Hoàng gia (số lượng như nhau đối với mỗi gia đình) đến ăn tiệc vào ngày Giáng sinh. Mỗi thành viên sẽ ăn đúng 1 hạt lúa mì.

Vì số lượng hạt lúa mì dự trữ của từng gia đình có thể khác nhau nên các gia đình Kiến đã cùng nhau thoả thuận, những hạt lúa mì trong mỗi gia đình ngoài việc dùng để đón tiếp các thành viên của Hoàng gia, nó còn dùng vào việc hỗ trợ chung bằng cách đem tặng cho những gia đình khác. Trong trường hợp đem tặng thì gia đình tặng phải vận chuyển những hạt lúa mì đến gia đình được tặng, mỗi 1 mét đường đi, những con kiến tham gia vận chuyển sẽ ăn 1 hạt lúa mì của gia đình tặng và không phụ thuộc vào số lượng vận chuyển.

Yêu cầu

Viết chương trình xác định số lượng tối đa K các thành viên của Hoàng Gia mà các gia đình kiến có thể đón tiếp (như nhau cho mọi gia đình).

Input

• Dòng 1: Ghi số nguyên N là số gia đình Kiến.
• N dòng tiếp theo: Dòng thứ i là thông tin về gia đình i, gồm 2 số Ai và Bi, Ai là vị trí sinh sống của gia đình kiến thứ i (bằng khoảng cách từ của hầm vào) và Bi là số lượng hạt lúa mì mà gia đình kiến thứ i gom nhặt được. Các gia đình được viết theo thứ tự trên đường hầm (từ ngoài vào trong).

Output

• Ghi số K (số lượng thành viên tối đa mà các gia đình kiến có thể tiếp đón).

Giới hạn

• 1 <= N <= 400 000
• 0 <= Ai, Bi <= 1 000 000 000
• Không có hai gia đình nào nằm ở cùng một vị trí

Ví dụ

Input
3 
20 100 
30 80
200 150

Output
85