#585. BIRTHDCAKE - Bánh sinh nhật

Bộ nhớ: 256 MiB Thời gian: 200 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: (Đề đề xuất DHBB 2017 của THPT CHUYÊN HẠ LONG)

Hôm nay là sinh nhật của Bờm! Biết Bờm rất thích ăn bánh nên bố Bờm đã chuẩn bị một bàn chất N chiếc bánh ngọt, các bánh được đánh số từ 1 đến N . Vì ăn quá nhiều bánh sẽ không tốt nên bố Bờm chỉ cho phép con mình ăn bánh trong thời gian T giây. Bờm 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ứ i được đặt ở tọa độ x_i trên đường thẳng. Thời gian để Bờm di chuyển từ vị trí tọa độ a đến vị trí toạ độ b |a - b| giây. Thời gian để Bờm ăn hết chiếc bánh thứ i t_i giây. Nếu như có nhiều chiếc bánh ở cùng một tọa độ thì Bờm không cần di chuyển, nhưng Bờm phải ăn từng cái một (có thể không căn hết tất cả bánh tại đó).

Ban đầu vị trí đứng của Bờm là ở gốc tọa độ O.

Yêu cầu: Hãy tính xem sau thời gian T giây Bờm 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 T được ghi cách nhau một dấu cách;
  • N dòng tiếp theo, dòng thứ i chứa hai số nguyên x_i t_i được ghi cách nhau một dấu cách. Các bánh được liệt kê theo thứ tự không giảm của tọa độ, nghĩa là nếu i < j thì x_i ≤ x_j .

Dữ liệu ra:

  • Một số nguyên duy nhất là số lượng bánh nhiều nhất mà Bờm có thể ăn trong thời gian T giây.

Ví dụ:

Dữ liệu vào:
3 10
1 4
2 6
3 3
Dữ liệu ra:
2
Giải thích:
  • Bờm đi đến tọa độ 1 và ăn chiếc bánh ở đó (mất tổng cộng 5 giây) sau đo đi đến tọa độ 3 và ăn chiếc bánh ở đó (mất thêm 2 + 3 giây nữa). Tổng cộng ăn được 2 bánh trong đúng 10 giây.

Giới hạn:

  • 1 ≤ N ≤ 10^5; 1 ≤ T, x_i, t_i ≤ 10^9 .