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