Mua hàng khuyến mãi

Nhân dịp năm mới 2020, trung tâm mua sắm HN mở một đợt khuyến mãi lớn. Bình là một khách hàng thân thiết, nên trung tâm gửi cho Bình một danh sách n loại mặt hàng khuyến mãi, được đánh số từ 1 đến n. Mặt hàng thứ i có giá khuyến mãi $x_i$ đồng, giá trị thực là $y_i$ đồng và số lượng là $z_i$ ($1 \le i \le n$).

Bình có số tiền m đồng để mua các loại mặt hàng khuyến mãi và mong muốn đạt được tổng giá trị thực của các loại mặt hàng có thể mua được là lớn nhất. Vì số lượng hàng khuyến mãi nhiều, nên Bình không biết phải chọn mua những loại mặt hàng nào, số lượng bao nhiêu cho phù hợp với số tiền của mình.

Yêu cầu: Hãy giúp Bình mua các loại mặt hàng của trung tâm mua sắm HN, sao cho không vượt quá số tiền m và đạt tổng giá trị thực của các loại mặt hàng có thể mua được là lớn nhất.

Vào từ tệp văn bản CAU4.INP:

• Dòng đầu tiên chứa hai số nguyên dương n và m ($1 \le n \le 500$, $1 < m \le 5 \times 10^4$);
• Dòng thứ i trong n dòng tiếp theo ghi ba số nguyên dương $x_i$, $y_i$ và $z_i$ lần lượt là giá trị khuyến mãi, giá trị thực và số lượng của loại mặt hàng thứ i ($1 \le x_i \le 10^4$, $1 \le y_i \le 10^4$, $1 \le z_i \le 100$, $1 \le i \le n$).

Ghi ra tệp văn bản CAU4.OUT:

• Dòng đầu là tổng giá trị đạt được;
• Dòng thứ i trong n dòng tiếp theo ghi số $k_i$ ($1 \le i \le n$) là số lượng loại mặt hàng thứ i được chọn mua. Nếu có nhiều cách chọn thỏa mãn, thì đưa ra cách chọn có chỉ số loại mặt hàng nhỏ nhất là nhiều nhất.

• $1 \le n \le 500$, $1 < m \le 5 \times 10^4$;
• $1 \le x_i \le 10^4$, $1 \le y_i \le 10^4$, $1 \le z_i \le 100$.