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

TAI NẠN

Một nhóm n học sinh đi dạo chơi trong rừng và bị trượt chân tụt xuống một hố sâu. Hố có độ sâu
d (1 ≤ d ≤ 105). Mọi người quyết định đứng lên vai nhau tạo thành một cái thang người để giúp
một số bạn ra khỏi hố, chạy về nhà nhờ người ra giúp đỡ. Mỗi học sinh biết chính xác độ cao cho
đến vai và chiều dài cánh tay của mình. Với học sinh thứ i, các chiều cao và độ dài đó là hi và
li, i=1,2, . . ., n (1 ≤ n ≤ 2 000, 1 ≤ hi, li ≤ 105). Nếu học sinh i đứng trên thang do các bạn
j1, j2, . . ., jk làm thì độ cao bạn đó với tới là hj1+hj2+ . . . +hjk+hi+li. Bạn i có thể thoát ra
khỏi hố nếu độ cao trên lớn hơn hoặc bằng d. Tất cả học sinh trong nhóm đều đủ khoẻ để làm
thang. Những bạn đã ra khỏi hố không giúp gì được cho các bạn còn lại.

Yêu cầu: Cho n, hi, li (i = 1  n) và d. Hãy xác định số lượng nhiều nhất các bạn thoát được
khỏi hố trước khi có sự giúp đỡ từ bên ngoài.

Dữ liệu: Vào từ file văn bản ADVENT.INP:
 Dòng đầu tiên chứa số nguyên n,
 Dòng thứ i trong n dòng sau: mỗi dòng chứa 2 số nguyên hi li,
 Dòng cuối cùng chứa số nguyên d.

Kết quả: Đưa ra file văn bản ADVENT.OUT:
 Ghi số nguyên m – số lượng người thoát được,

ADVENT.INP ADVENT.OUT
6 4
6 7
3 1
8 5
8 5
4 2
10 5
30