Có N đội tham gia một cuộc thi giải đố. Nếu một đội nào đấy giải được 1 câu đố thì sẽ được 1 quả bóng bay. Do đó thứ hạng của một đội nao đó sẽ là số lượng đội có nhiều bóng bay hơn cộng 1. Ví dụ nếu có 7 đội có nhiêu bóng bay hơn thì bạn sẽ đứng thứ 8 và có thể có nhiêu đội có thứ hạng như nhau.
Có một việc quan trọng là phải ăn uống đầy đủ trước khi đi thi. Nêu số lượng bóng bay lớn hơn cân nặng của 1 đội thì đội đấy sẽ bay lơ lửng và chạm vào trần nhà - điều mà bị cấm khi tham gia và sẽ bị loại khỏi cuộc thi và mất tên trên bảng xếp hạng.
Trong N đội tham gia, đội thứ i có số bóng bay là ti và có cân nặng là wj. Đảm bảo rằng ti không vượt quá wi nên không đội nào lơ lửng từ đầu cuộc chơi.
Bờm là một thành viên trong đội 1. Anh ấy không thích ăn gian và sẽ không bao giờ lấy bóng bay của đội khác. Tuy nhiên, anh ấy có thể tặng bóng bay cho đội khác (Hiển nhiên rằng anh ấy không thể tặng quá số lượng bóng bay của đội anh ấy).
Yêu cầu: Hãy tính thứ hạng tốt nhất mà Bờm có thể đạt được.
Dữ liệu: Có cấu trúc như sau:
- Dòng đầu tiên chứ số N (1 ≤ N ≤ 3.105) là số đội tham gia cuộc thi;
- N dòng tiếp theo, dòng thứ i gồm 2 số ti và wi (0 ≤ ti ≤ wi ≤ 1018) lần lượt là số bóng bay và cân nặng của đội thứ i. Bờm là thành viên của đội 1.
Kết quả: Một số duy nhất là thứ hạng tốt nhất Bờm có thể đạt được.
|
Input |
Output |
|
8 20 1000 32 37 40 1000 45 50 16 16 16 16 14 1000 2 1000 |
3 |
Giải thích: Ban đầu Bờm có 20 quả bóng bay. Có 3 đội có hơn bóng bay là 32, 40 và 45, nên đội Bờm đứng thứ 4. Có một chiến thuật là:
1. Bờm đưa 6 quả bóng bay cho đội 32 quả và nặng 37, vừa đủ để khiến đội đó lơ lửng, tuy nhiên Bờm chỉ còn lại 14 quả và đứng thứ 5.
2. Bờm đưa 6 quà cho đội 45 quả. Do đó đội này cũng bị lơ lửng và bị loại.
3. Bờm đưa cho mỗi đội có 16 quả 1 quả bóng bay và 2 đội đấy bị loại.
4. Bờm còn lại 20 - 6 - 6 - 1 - 1 = 6 quả.
5. Còn lại 3 đội với số lượng bóng bay mỗi đội lần lượt là 40, 14 và 2.
6. Bờm sẽ xếp thứ 3 vì có 2 đội có nhiều bóng bay hơn.