Cửa sổ huấn luyện theo bảng xếp hạng

Bối cảnh

Một trung tâm huấn luyện có n học viên. Mỗi học viên được mô tả bởi score và cost — chi phí cần để đưa học viên đó vào một đợt huấn luyện. Trước hết, học viên được xếp theo score giảm dần; nếu score bằng nhau, cost nhỏ hơn đứng trước. Sau ranking, ban tổ chức chỉ được chọn một đoạn liên tiếp theo rank để giữ nhóm có mức năng lực tương đối liền kề. Tổng cost của đoạn không được vượt ngân sách K.

Hãy tìm đoạn có nhiều học viên nhất. Nếu nhiều đoạn cùng độ dài, chọn đoạn có rank bắt đầu nhỏ hơn. Cost đều không âm nên khi mở rộng right làm tổng vượt K, dịch left sang phải chỉ làm tổng giảm; đó là invariant cho sliding window. Bài Advanced này cố ý đặt sliding window ở đúng phần OPTIONAL/ADV của B17, đồng thời buộc người học giữ đúng pipeline: comparator → sort → window trên state ranking. Không dùng struct; có thể lưu record bằng pair<score,cost>.

Sau ranking, bạn không còn được thay đổi thứ tự học viên để tối ưu ngân sách; chỉ được chọn một đoạn liên tiếp. Vì vậy sort và sliding window thuộc hai pha khác nhau của pipeline. Nếu chạy window trên input gốc rồi mới sort, bạn đang giải một bài hoàn toàn khác. Bài này đặc biệt nhấn mạnh khái niệm "state sau biến đổi" vốn là chủ đề xuyên suốt B17–B18.

Yêu cầu

1. Đọc n K và n cặp score cost.
2. Sort score giảm; tie cost tăng.
3. Trên ranking, tìm đoạn liên tiếp dài nhất có tổng cost≤K bằng sliding window.
4. Tie độ dài chọn L nhỏ hơn.
5. In length L R theo rank 1-based.

Yêu cầu tổ chức code

Sliding window chỉ dùng ở bài ADV; không coi là prerequisite cho bài CORE.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng công cụ của buổi và không vượt prerequisite.

Input

Dòng 1 n K; n dòng score cost.

Output

Một dòng length L R.

Ràng buộc

1≤n≤5000, 0≤cost,K≤10^18, score trong long long.

Ví dụ 1

Input

6 10
100 4
90 3
95 5
80 2
90 4
70 1

Output

4 3 6

Giải thích

Ranking theo score là (100,4),(95,5),(90,3),(90,4),(80,2),(70,1). Window đầu có cost 4+5=9 dài 2; thêm 3 thành 12 vượt K nên left dịch. Đoạn ranks 2..4 có cost 5+3+4=12 vẫn vượt, sau điều chỉnh ta tìm được đoạn ranks 3..6 có cost 3+4+2+1=10 dài 4. Không đoạn nào dài hơn, nên output 4 3 6.

Ví dụ 2

Input

3 0
10 1
9 2
8 3

Output

0 -1 -1

Giải thích

K=0 trong khi ba học viên có cost lần lượt 1,2,3, đều dương. Mỗi khi right thêm một phần tử, sum lập tức lớn hơn 0 nên vòng while phải loại phần tử từ left cho đến khi window rỗng. Không có đoạn không rỗng nào đạt ngân sách. Biến bestLen vì thế giữ 0 và bài quy ước in 0 -1 -1 thay vì một rank giả.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: nested pair, custom comparator, ranking, sliding window, nonnegative costs, tie-break
• Giới hạn kiến thức: B01-B17 + OPTIONAL B17
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100