Tuần cuối học kỳ, bạn Minh còn ~n~ bài tập lớn chưa làm. Bài thứ ~i~ cần đúng ~t_i~ phút để hoàn thành và có hạn nộp là thời điểm ~d_i~ (tính bằng phút, kể từ bây giờ – thời điểm ~0~).

Minh bắt đầu làm từ thời điểm ~0~, làm lần lượt từng bài: xong hẳn bài này mới chuyển sang bài khác, giữa các bài không nghỉ; thứ tự làm các bài do Minh tự chọn. Nếu bài thứ ~i~ được hoàn thành tại thời điểm ~f_i~ thì độ trễ của bài đó là ~\max(0,\ f_i - d_i)~ phút: xong đúng hạn hoặc trước hạn thì độ trễ bằng ~0~.

Vì mỗi phút nộp muộn đều bị trừ điểm, Minh muốn bài bị trễ nhiều nhất cũng chỉ trễ ít nhất có thể.

Yêu cầu

Hãy chọn thứ tự làm ~n~ bài sao cho độ trễ lớn nhất trong ~n~ bài là nhỏ nhất, và đưa ra giá trị nhỏ nhất đó.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~n~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~t_i~ và ~d_i~.

Kết quả ra

Ghi ra một số nguyên duy nhất là giá trị nhỏ nhất có thể của độ trễ lớn nhất.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~1 \le t_i, d_i \le 10^9~.

• Subtask 1 (10% số điểm – test 01–03): ~n \le 8~ và ~t_i, d_i \le 10^6~;
• Subtask 2 (20% số điểm – test 04–08): mọi ~d_i~ bằng nhau;
• Subtask 3 (25% số điểm – test 09–13): ~n \le 2000~;
• Subtask 4 (45% số điểm – test 14–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

3
3 6
2 8
4 5

Kết quả ra mẫu 1

1

Giải thích

Làm theo thứ tự bài ~3~, bài ~1~, bài ~2~: các bài lần lượt hoàn thành tại các thời điểm ~4~, ~7~, ~9~, trong khi hạn nộp tương ứng là ~5~, ~6~, ~8~, nên độ trễ lần lượt là ~0~, ~1~, ~1~; độ trễ lớn nhất bằng ~1~.

Không có thứ tự nào tốt hơn: dù làm theo thứ tự nào thì bài làm sau cùng cũng xong tại thời điểm ~3 + 2 + 4 = 9~, mà hạn nộp muộn nhất là ~8~, nên bài đó trễ ít nhất ~1~ phút. Ngược lại, nếu làm "bài ngắn trước" (bài ~2~, bài ~1~, bài ~3~) thì bài ~3~ xong tại thời điểm ~9~ và trễ tới ~4~ phút.