Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

BTKCATU2 – CÁI TÚI 2

Trong siêu thị tại gian hàng Black Friday có ~n~ đồ vật, đồ vật thứ ~i~ có trọng lượng là ~W[i]~ và giá trị ~V[i]~. Bạn được một phiếu mua hàng đặc biệt khi vào mua hàng tại gian hàng Black Friday ở siêu thị này. Khi sử dụng phiếu mua hàng này bạn được phép chọn một số đồ vật bất kỳ trên gian hàng miễn sao trọng lượng tối đa là ~M~. Hỏi bạn có thể lấy đi những mặt hàng nào để giá trị bạn nhận được là tối đa.

Bạn hãy lập trình giải quyết bài toán trên với dữ liệu cho là danh sách ~n~ mặt hàng tại gian hàng mà bạn có thể chọn. Bạn cần liệt kê được danh sách các mặt hàng mà mình lấy được.

Dữ liệu vào

• Dòng đầu tiên là hai số nguyên dương ~n~ và ~M~ ~(1 \le n \le 24;\ 1 \le M \le 10^{11})~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~w[i]~ và ~v[i]~ là trọng lượng và giá trị của đồ vật thứ ~i~ ~(1 \le w[i], v[i] \le 10^9)~.

Kết quả

• Dòng 1 in một số nguyên ~x~ là số đồ vật bạn lấy được.
• Dòng 2 bạn in số thứ tự của các vật phẩm được lấy đi (số thứ tự của các đồ vật theo thứ tự trong đầu vào).
• Nếu có nhiều đáp án tối ưu, bạn có thể in đáp án tối ưu bất kỳ.

Giới hạn

• ~1 \le n \le 24~, ~1 \le M \le 10^{11}~, ~1 \le w[i], v[i] \le 10^9~.
• Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 128 MB.

Sample Input 1

5 20
7 1
5 8
1 1
7 8
9 7

Sample Output 1

4
1 2 3 4

Giải thích

Lấy đồ vật 1, 2, 3 và 4: tổng trọng lượng ~7 + 5 + 1 + 7 = 20 \le 20~, tổng giá trị ~1 + 8 + 1 + 8 = 18~ là lớn nhất.