Cho \(n\) đồ vật có khối lượng lần lượt là \(a_1, a_2... a_n\) giá trị lần lượt là \(v_1, v_2... v_n\) và số lượng mỗi loại vật lần lượt là \(c_1, c_2... c_n\). Cho một ba lô có tải trọng là \(m\).

Yêu cầu: Chọn một số đồ vật để vào ba lô sao cho tổng khối lượng không vượt quá \(m\) và tổng giá trị của các đồ vật là lớn nhất.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương \(n\) và \(m\) \((n \le 100, m \le 10^4)\)
• Dòng thứ i trong n dòng tiếp theo, mỗi dòng ghi ba số nguyên dương \(a_i, v_i, c_i (a_i, c_i \le 1000, c_i \le 10)\)

Dữ liệu ra:

• Một số là kết quả tìm được

Input

6 30
2 1 3
4 10 2
7 10 7
4 7 1
1 2 4
9 12 6

Output

55