Ẩm thực (Trại hè MB 2019)

Xem PDF

Điểm: 300 (p) Thời gian: 1.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong ngày hội văn hóa ẩm thực, người ta chọn một con đường để bày các quán ăn nhằm phục vụ các du khách miễn phí. Có tất cả \(n\) quán ăn đánh số từ \(1\) tới \(n\), quán ăn thứ \(i\) nằm cách đầu đường \(x_i\) mét, quán có một món ăn duy nhất và để ăn món ăn đó du khách cần \(a_i\) giây.

Mỗi du khách sẽ đi vào từ đầu đường, thời gian để du khách di chuyển \(1\) mét đúng bằng \(1\) giây, khách có thể dừng lại quán trên đường để thưởng thức món ăn miễn phí của quán đó, tuy nhiên du khách không được phép bỏ dở món ăn. Sau \(T\) giây tính từ lúc đi vào con đường ẩm thực, du khách đó sẽ không được ăn miễn phí nữa.

Yêu cầu: Hãy giúp du khách chọn quán để có thể thưởng thức miễn phí món ăn tại nhiều quán nhất.

Input:

Vào từ file văn bản FREEFOOD.INP

  • Dòng \(1\) chứa hai số nguyên dương \(n < 10; T < 10^{18}\)
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(x_i, a_i (a_i < 10^9\), các \(x_i\) được xếp theo thứ tự tăng đần \(x_1 < x_2 <...< x_n \le 10^9)\)

Output:

  • Ghi ra file văn bản FREEFOOD.OUT một số nguyên duy nhất là số quán tối đa được chọn để ăn miễn phí.

Example:

Test 1

Input
4 10
1 5
2 1
3 3
4 2
Output
3

Bình luận

Không có bình luận nào.