Nhân dịp năm mới 2020, trung tâm mua sắm HCN 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ết mãi, được đánh số từ 1 đến n. Mặt hàng thứ i có giá khuyến mãi xi đồng, giá trị thực là yi đồng và số lượng là zi (1 ≤ i ≤ 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 HCN, 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.

Dữ liệu vào:

• Dòng dầu tiên chứa hai số nguyên dương n và m (1 ≤ n ≤ 500, 1 <m ≤ 5x10^4);</p>

• Dòng thứ i trong n đòng tiếp theo ghi ba số nguyên dương xi, yi và zi, 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 ≤ xi ≤ 10^4, 1 ≤ y ≤ 10^4, 1 ≤ zi ≤ 100, 1 ≤ i ≤ n).

Kết quả: In ra màn hình

• Đòng đầu là tổng giá trị đạt được;

• Dòng thứ i trong n dòng tiếp theo ghi số ki (1 ≤ i ≤ 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 thoa 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.

Input:

5 14
9 10 1
2 3 3
2 3 3 
3 6 4
5 10 4

Output:

28
0
0
0
3
1

Giải thích: Bình chọn 3 loại mặt hàng thứ 4 và một loại mặt hàng thứ 5, tổng giá trị là 28