Lại thích khể ở đây nên chim thần lại đến. Lần này chim thần chở Thái em đến đảo đá quý. Khổ nỗi cái gì lấy nhiều rồi cũng hết. Trên hòn đảo bây giờ chỉ còn \(N\) loại đá quý, mỗi loại chỉ còn một số lượng nhất định. Loại thứ \(i\) có trọng lượng là \(w_1\), có giá trị là \(v_1\), và có số lượng là \(a_1\). Thái em mang theo túi nặng có thể chứa tối đa trọng lượng là \(M\). Hỏi tổng giá trị tối đa của các viên đá quý mà Thái em có thể mang về là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên ghi hai số \(N\) và \(M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) ghi ba số \(w_i\), \(v_i\), \(a_i\) lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ \(i\).

Kết quả

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà Thái em có thể mang về.

Ràng buộc

• \(1 \le N \le 100\)
• \(1 \le M \le 10^4\)
• \(0 \le w_i \le 10^3\)
• \(0 \le v_i \le 10^4\)
• \(0 \le a_i \le 10^3\)

Input 1

3 4
1 4 2
2 7 2
3 6 1

Output 1

15