Khác với lần trước, lần này chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng là ~a_i~. Lần này Zayzen123 mang theo túi "năm trăm gang" 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à zayzen123 có thể mang về là bao nhiêu?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• 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 ~(0 ≤ w_i, v_i , a_i ≤ 10^3)~

Output:

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

Example:

input

3 4 
1 4 2 
2 7 2 
3 6 1   

output

15