Hội nghị II

Nông trại có $N$ con bò, được đánh số từ $1$ đến $N$ theo thứ tự thâm niên: bò $1$ là con thâm niên nhất, bò $N$ là con ít thâm niên nhất.

Trong chuồng chỉ có đúng một máng cỏ, nên tại mỗi thời điểm chỉ một con bò được ăn. Bò $i$ đi tới máng vào thời điểm $a_i$ và khi được vào ăn thì nó chiếm máng trong đúng $t_i$ đơn vị thời gian.

Máng hoạt động theo quy tắc sau:

• Nếu máng đang trống và không có con bò nào đang đợi, máng nằm yên cho tới thời điểm con bò kế tiếp đi tới.
• Mỗi khi máng trống, trong số những con bò đã đi tới nhưng chưa được ăn, con thâm niên nhất (chỉ số nhỏ nhất) sẽ vào ăn ngay lập tức.
• Một con bò đi tới đúng vào thời điểm máng vừa trống vẫn được tính là đang đợi và có thể được chọn ngay tại thời điểm đó.

Thời gian chờ của một con bò là khoảng thời gian tính từ lúc nó đi tới máng cho tới lúc nó bắt đầu ăn. Hãy tính thời gian chờ lớn nhất trong số $N$ con bò.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $t_i$.

Dữ liệu ra

Một số nguyên duy nhất là thời gian chờ lớn nhất.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le a_i\le {10}^9$
• $1\le t_i\le {10}^5$
• Các thời điểm $a_i$ không nhất thiết phân biệt.
• Đáp số có thể vượt quá phạm vi số nguyên 32 bit.

Ví dụ