Bạn đã từng nghe đến công ty Just Odd Inventions chưa? Công việc của công ty này là tạo ra “những phát minh kỳ quặc” (just odd inventions). Ta gọi tắt công ty là JOI.

Công ty JOI đang nghiên cứu cách nhốt nhiều vi sinh vật còn sống trong cùng một đĩa Petri. Có \(N\) vi sinh vật cần nghiên cứu, được đánh số \(1,2,\ldots,N\). Khi bị nhốt vào đĩa Petri, mỗi vi sinh vật lập tức giải phóng một chất độc hại gọi là foo (fatally odd object). Lượng foo mà mỗi vi sinh vật giải phóng đã được biết trước. Toàn bộ lượng foo do các vi sinh vật trong đĩa giải phóng được chia đều để các vi sinh vật đó hấp thụ. Khả năng chịu đựng foo của mỗi vi sinh vật cũng đã được biết trước; nếu hấp thụ một lượng lớn hơn ngưỡng này, vi sinh vật sẽ chết.

Vi sinh vật \(i\) giải phóng \(a_i\) miligam foo và chịu được tối đa \(b_i\) miligam foo. Nói cách khác, nếu nhốt các vi sinh vật \(i_1,i_2,\ldots,i_k\) vào đĩa Petri, mỗi vi sinh vật trong đĩa sẽ hấp thụ lượng foo, tính bằng miligam, bằng

Vi sinh vật \(i\) trong đĩa sẽ chết nếu lượng hấp thụ này lớn hơn \(b_i\).

Theo yêu cầu của công ty JOI, bạn phải nhốt càng nhiều vi sinh vật còn sống vào cùng một đĩa Petri càng tốt. Tuy nhiên, xác vi sinh vật sẽ ảnh hưởng xấu đến môi trường trong đĩa, nên không được để bất kỳ vi sinh vật nào trong đĩa chết do hấp thụ foo.

Việc công ty JOI kiếm lợi nhuận bằng cách tạo ra “những phát minh kỳ quặc” như thế nào vẫn là một bí ẩn; ngay cả trong công ty cũng không ai ngoài giám đốc biết được điều đó.

Yêu cầu

Cho số lượng vi sinh vật cần nghiên cứu, lượng foo giải phóng và ngưỡng chịu đựng foo của từng vi sinh vật, hãy viết chương trình tìm số vi sinh vật lớn nhất có thể nhốt vào cùng một đĩa Petri mà không vi sinh vật nào chết.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số vi sinh vật cần nghiên cứu.
• \(N\) dòng tiếp theo mô tả các vi sinh vật. Dòng \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên dương \(a_i,b_i\), cách nhau bởi dấu cách, lần lượt là lượng foo mà vi sinh vật \(i\) giải phóng và ngưỡng chịu đựng foo của nó, tính bằng miligam.

Dữ liệu ra

Ghi ra đầu ra chuẩn trên một dòng số vi sinh vật lớn nhất có thể nhốt vào cùng một đĩa Petri mà không vi sinh vật nào chết.

Ràng buộc

• \(1\le N\le300000=3\times10^5\).
• \(1\le a_i\le100000=10^5\) với mọi \(1\le i\le N\).
• \(1\le b_i\le100000=10^5\) với mọi \(1\le i\le N\).
• Giới hạn thời gian: \(1.5\) giây. Giới hạn bộ nhớ: \(256\) MB.

Lưu ý

Các số nguyên cần xử lý trong bài này có thể vượt quá phạm vi biểu diễn của kiểu số nguyên \(32\) bit.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) nhóm dữ liệu, mỗi nhóm \(10\) điểm. Mỗi nhóm gồm nhiều bộ dữ liệu; chỉ nhận được điểm của nhóm nếu trả lời đúng tất cả các bộ dữ liệu trong nhóm đó.

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le1000\).

Ví dụ

6
12 8
5 9
2 4
10 12
6 7
13 9

3