Mô tả và yêu cầu

Hôm nay là sinh nhật của Khánh! Biết Khánh rất thích ăn bánh nên bố Khánh
đã chuẩn bị một bàn chất 𝑁 chiếc bánh ngọt, các bánh được đánh số từ 1 đến 𝑁. Vì
ăn quá nhiều một loại bánh sẽ không tốt nên bố Khánh chỉ cho phép con mình ăn
bánh trong thời gian 𝑇 giây. Khánh thì lại muốn mình ăn thật nhiều bánh cho thỏa
thích.
Bàn bánh có thể xem như một trục số gốc tọa độ là O, chiếc bánh thứ 𝑖 được
đặt ở tọa độ 𝑥𝑖 trên đường thẳng. Thời gian để Khánh di chuyển từ vị trí chiếc bánh
thứ 𝑖 đến chiếc bánh thứ 𝑗 là |𝑥𝑗 − 𝑥𝑖| giây. Thời gian để Khánh ăn hết chiếc bánh
thứ 𝑖 là 𝑡𝑖 giây. Nếu như có nhiều chiếc bánh ở cùng một tọa độ thì Khánh không cần
di chuyển, nhưng Khánh phải ăn từng cái một.
Ban đầu vị trí đứng của Khánh là ở gốc tọa độ O.
Yêu cầu: Hãy tính xem sau thời gian 𝑇 giây Khánh có thể ăn được nhiều nhất
bao nhiêu chiếc bánh ngọt.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên N và T (1 ≤ N ≤ 105; 1 ≤ T ≤ 109) theo thứ
tự là số lượng bánh và hạn chế thời gian để Khánh ăn bánh.
• Dòng thứ 𝑖 trong số 𝑁 dòng tiếp theo chứa hai số nguyên 𝑥𝑖 và 𝑡𝑖 (1 ≤ 𝑥𝑖, 𝑡𝑖 ≤
109) là tọa độ của chiếc bánh thứ 𝑖 và thời gian để Khánh ăn hết chiếc bánh này. Các
bánh được liệt kê theo thứ tự không giảm của tọa độ, nghĩa là nếu 𝑖 < 𝑗 thì 𝑥𝑖 ≤ 𝑥𝑗.
• Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

• Ghi ra file thiết bị xuất chuẩn trên một dòng duy nhất, một số nguyên là số
lượng bánh nhiều nhất mà Khánh có thể ăn trong thời gian 𝑇 giây.

Ví dụ

INPUT                     OUTPUT

                      3 10                          2
                      1 4
                      2 6
                      3 3

Giải thích: Trong ví dụ Khánh di chuyển từ tọa độ 0 đến tọa độ 1 và ăn chiếc bánh
ở đó, tiếp theo di chuyển đến tọa độ 3 ăn chiếc bánh thứ 3. Ràng buộc:
    •  Có 30% số test ứng với 30% số điểm của bài có 1 ≤ 𝑁 ≤ 20 và 1 ≤ 𝑇 ≤ 109.
    •  Có 30% số test ứng với 30% s          ố điểm của bài có 1 ≤ 𝑁 ≤ 1000 và 1 ≤ 𝑇 ≤
       1000.
    •  Có 40% số test còn lại ứng với 40% số điểm của bài có 1 ≤ 𝑁 ≤ 105 và 1 ≤
       𝑇 ≤ 109.