Bạn có W đô la trong tay và muốn thuê được càng nhiều công nhân càng tốt. Bạn tự quyết định sẽ thuê những ai và trả lương cho họ như thế nào, nhưng bạn phải đảm bảo mức lương tối thiểu trả cho công nhân mà bạn thuê, và bạn cũng phải tuân thủ các quy định trong ngành xây dựng. Bạn còn phải thu xếp chi trả trong phạm vi ngân sách W đô la của mình.

Theo bản chất của dự án, trình độ tay nghề của công nhân hoàn toàn không ảnh hưởng, vì vậy bạn chỉ quan tâm đến việc cực đại hóa số công nhân bạn thuê, bỏ qua việc xét đến trình độ của họ. Tuy nhiên, nếu có nhiều hơn một cách thuê để đạt được số lượng này, thì bạn phải chọn cách sao cho tổng số tiền phải trả cho công nhân của bạn là ít nhất có thể. Trong trường hợp có nhiều hơn một cách như vậy, bạn có thể chọn bất kì cách nào.

BÀI TOÁN

Biết các yêu cầu về lương cũng như trình độ tay nghề của các ứng viên và số tiền bạn có, hãy viết chương trình xác định những ứng viên bạn cần thuê. Bạn phải thuê càng nhiều công nhân càng tốt và bạn phải thực hiện việc này sao cho bạn tốn càng ít tiền càng tốt mà không vi phạm các quy định của ngành xây dựng mô tả ở trên.

RÀNG BUỘC

1 ≤ N ≤ 500000 Số lượng ứng viên.

1 ≤ S_k ≤ 20000 Yêu cầu về lương tối thiểu của ứng viên k.

1 ≤ Q_k ≤ 20000 Trình độ tay nghề của ứng viên k.

1 ≤ W ≤ 10000000000 Tổng số tiền bạn có.

Chương trình của bạn phải đọc từ standard input dữ liệu sau:

Dòng đầu chứa các 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 trên một dòng. Dòng thứ k trong các dòng này mô tả ứng viên thứ k và chứa các số nguyên Sk và Qk, cách nhau bởi một dấu cách.

OUTPUT

Chương trình của bạn phải ghi ra standard output dữ liệu sau:

Dòng đầu tiên chứa một số nguyên H, là số công nhân mà bạn thuê.

H dòng tiếp theo liệt kê số hiệu của các ứng viên mà bạn chọn thuê (mỗi người trong họ ứng với một số nguyên khác nhau trong khoảng từ 1 đến N), mỗi người trên một dòng, theo thứ tự bất kì.

CÁCH CHẤM ĐIỂM

Với mọi test, bạn sẽ nhận được trọn điểm của test nếu chọn lựa của bạn cho phép bạn thỏa mãn mọi mục đích của mình đồng thời tuân thủ mọi ràng buộc. Nếu bạn sinh ra một output file với dòng đầu tiên chính xác (tức là cho đúng giá trị H), nhưng mô ta cách thuê không đúng, bạn sẽ nhận được 50% số điểm của test đó. Điều này vẫn đúng ngay cả khi output file có format không đúng, miễn sao dòng đầu tiên là chính xác.

Có một nhóm các test với tổng số điểm là 50, N sẽ không vượt quá 5000.

VÍ DỤ

Chỉ có duy nhất một cách chọn để bọn có thể thuê 2 công nhân và vẫn thỏa mãn tất cả các ràng buộc là chọn công nhân 2 và 3. Bạn phải trả cho họ tương ứng là 80 và 8 đô la và như vậy vẫn nằm trong ngân sách 100 đô la của bạn.

Ở đây, bạn có thể thuê tất cả 3 công nhận. Bạn trả 1 đô la cho công nhân 1 và 1.50 đô la cho mỗi công nhân 2 và 3, và bạn đã thuê được tất cả các công nhân với ngân sách 4 đô la mà bạn có.

Ở đây, bạn không thể thuê tất cả 3 công nhân, vì giá thuê sẽ lên đến 60 đô la, nhưng bạn có thể thuê được 2 người bất kì trong họ. Bạn chọn thuê công nhân số 2 và số 3 vì tổng số tiền thuê sẽ là thấp nhất, nếu so sánh với các cách thuê 2 công nhân khác. Bạn có thể trả 10 đô la cho công nhân số 2 và 15 đô la cho công nhân số 3. Chi phí tổng cộng là 25 đô la. Nếu bạn thuê công nhân số 1 và số 2 thì số tiền phải trả ít nhất tương ứng là 10 và 20 đô la. Nếu bạn thuê công nhân số 1 và số 3 số tiền phải trả ít nhất tương ứng là 10 và 30 đô la.

School@net