#5447. Hành trình nhiên liệu (FUELTRIP)

Một công ty công nghệ đang triển khai một nhiệm vụ thám hiểm trên bề mặt một hành tinh xa lạ. Có robot dò đường đặt tại các vị trí trên trục tọa độ. Robot thứ ban đầu có đơn vị nhiên liệu.

Trong suốt hành trình, đoàn robot chỉ có thể tiếp tục tiến lên đường thẳng nếu tất cả đều còn nhiên liệu. Diễn biến vận hành như sau:

• Nếu mọi robot đều có nhiên liệu , toàn bộ đoàn sẽ tiến lên đơn vị, và mỗi robot tiêu hao nhiên liệu.

• Nếu tồn tại robot cạn nhiên liệu, toàn bộ hành trình phải dừng lại vĩnh viễn.

Dọc tuyến đường có trạm nạp năng lượng. Trạm thứ nằm tại vị trí , chứa đơn vị nhiên liệu. Robot đứng đúng vị trí trạm có thể nạp thêm một lượng nguyên , làm:

• Năng lượng robot tăng thêm ,

• Nhiên liệu của trạm giảm xuống .

Các robot có thể tự do quyết định lượng nhiên liệu nạp sao cho tổng hành trình đi được là lớn nhất.

Yêu cầu: Hãy xác định số bước di chuyển tối đa mà đoàn robot có thể thực hiện.

Dữ liệu:

• Dòng đầu chứa hai số nguyên .

• dòng tiếp theo, mỗi dòng gồm .

• dòng tiếp theo, mỗi dòng gồm .

Dữ liệu bảo đảm: Không có hai robot ở cùng vị trí. Không có hai trạm ở cùng vị trí. Không robot nào xuất phát tại vị trí của trạm.

Kết quả: Ghi ra một số nguyên duy nhất là số bước tối đa có thể thực hiện.

Ví dụ:

Dữ liệu:

3 5
7 3
2 4
9 5
3 2
8 1
6 3
1 3
10 2

Kết quả:

5

Giới hạn:

• Subtask 1 ( số điểm): .

• Subtask 2 ( số điểm): .

• Subtask 3 ( số điểm): .

• Subtask 4 ( số điểm): .

• Subtask 5 ( số điểm): Không ràng buộc thêm.