Bạn cần thuê công nhân cho một dự án xây dựng. Có \(N\) ứng viên xin việc, được đánh số từ \(1\) đến \(N\). Mỗi ứng viên \(k\) yêu cầu được trả ít nhất \(S_k\) đô la nếu được thuê. Ngoài ra, ứng viên \(k\) có trình độ chuyên môn \(Q_k\). Quy định của ngành xây dựng yêu cầu tiền công của những người được thuê phải tỉ lệ với trình độ chuyên môn của họ. Ví dụ, nếu bạn thuê hai công nhân \(A\) và \(B\) với \(Q_A = 3Q_B\), bạn phải trả cho \(A\) đúng gấp ba lần số tiền trả cho \(B\). Bạn được phép trả số tiền không nguyên, kể cả những số tiền không thể biểu diễn bằng số thập phân hữu hạn, chẳng hạn một phần ba hoặc một phần sáu đô la.

Bạn có \(W\) đô la và muốn thuê càng nhiều công nhân càng tốt. Bạn được quyết định thuê ai và trả cho họ bao nhiêu, nhưng phải đáp ứng yêu cầu tiền công tối thiểu của những người được chọn, tuân thủ quy định của ngành và không vượt quá ngân sách \(W\) đô la.

Do tính chất của dự án, trình độ chuyên môn hoàn toàn không quan trọng, nên bạn chỉ quan tâm đến việc tối đa hóa số công nhân mà không xét đến trình độ của họ. Tuy nhiên, nếu có nhiều cách đạt được số công nhân lớn nhất, bạn muốn chọn cách có tổng số tiền phải trả nhỏ nhất. Nếu vẫn có nhiều cách như vậy, bạn có thể chọn bất kỳ cách nào.

Nhiệm vụ

Cho yêu cầu tiền công tối thiểu và trình độ chuyên môn của từng ứng viên, cùng số tiền bạn có, hãy viết chương trình xác định những ứng viên cần thuê. Bạn phải thuê nhiều người nhất có thể và trả tổng số tiền ít nhất có thể cho số người đó, đồng thời tuân thủ quy định của ngành nêu trên.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(W\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả các ứng viên, mỗi ứng viên một dòng. Dòng thứ \(k\) trong số này mô tả ứng viên số \(k\), chứa hai số nguyên \(S_k\) và \(Q_k\), cách nhau bởi một dấu cách.

Dữ liệu ra

Chương trình ghi ra đầu ra chuẩn:

• Dòng đầu chứa một số nguyên \(H\), là số công nhân bạn thuê.
• \(H\) dòng tiếp theo liệt kê số hiệu của các ứng viên bạn chọn thuê, mỗi người một dòng, theo thứ tự bất kỳ. Các số hiệu phải đôi một khác nhau và nằm trong khoảng từ \(1\) đến \(N\).

Ràng buộc

• \(1 \le N \le 500\,000\): số ứng viên.
• \(1 \le S_k \le 20\,000\): tiền công tối thiểu mà ứng viên \(k\) yêu cầu.
• \(1 \le Q_k \le 20\,000\): trình độ chuyên môn của ứng viên \(k\).
• \(1 \le W \le 10\,000\,000\,000\): số tiền bạn có.

Lưu ý quan trọng: Giá trị lớn nhất của \(W\) không thể lưu bằng \(32\) bit. Để lưu \(W\) trong một biến, bạn phải dùng kiểu dữ liệu \(64\) bit, chẳng hạn long long trong C/C++ hoặc int64 trong Pascal.

Phân nhóm

Bài có tổng cộng \(100\) điểm. Với mỗi test, bạn nhận toàn bộ điểm của test đó nếu tập ứng viên được chọn đạt được tất cả các mục tiêu và thỏa mãn mọi ràng buộc. Nếu kết quả có dòng đầu đúng, tức giá trị \(H\) đúng, nhưng không đáp ứng đầy đủ mô tả ở trên, bạn nhận \(50\%\) số điểm của test đó. Quy tắc này vẫn áp dụng ngay cả khi kết quả không đúng định dạng, miễn là dòng đầu đúng.

Trong một số test có tổng cộng \(50\) điểm, \(N\) không vượt quá \(5000\).

Ví dụ

4 100
5 1000
10 100
8 10
20 1

2
2
3

3 4
1 2
1 3
1 3

3
1
2
3

3 40
10 1
10 2
10 3

2
2
3

Nguồn

IOI 2009.