Có \(N\) công việc cần xử lý. Công việc thứ \(i\) (\(1 \le i \le N\)) yêu cầu dùng \(T_i\) ngày để thực hiện và có hạn chót vào ngày \(D_i\).

Bạn bắt đầu làm việc từ ngày \(0\) và tại mỗi thời điểm chỉ có thể làm duy nhất một công việc. Bạn có quyền chọn làm hoặc bỏ qua bất kỳ công việc nào, cũng như tự quyết định thứ tự thực hiện các công việc đã chọn. Một công việc được xem là hoàn thành đúng hạn nếu tổng số ngày làm việc, tính từ ngày \(0\) cho đến khi làm xong công việc đó, không vượt quá hạn chót.

Yêu cầu: Hãy tính số lượng công việc lớn nhất mà bạn có thể hoàn thành đúng hạn.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(T_i\) và \(D_i\) (\(1 \le T_i, D_i \le 10^9\)) mô tả thời gian cần thiết và hạn chót của công việc thứ \(i\).

Output

• In ra một số nguyên duy nhất là số lượng công việc tối đa hoàn thành đúng hạn.

Example

4
2 5
4 6
3 6
2 7

3

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(N \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 2000\).
• Subtask \(3\) (\(30\%\) số điểm): \(N \le 10^5\) và thời gian làm mọi công việc đều bằng nhau (\(T_i = 1\) với mọi \(i\)).
• Subtask \(4\) (\(35\%\) số điểm): Không có ràng buộc gì thêm.