Đá quý còn lại

Chú bé được chim thần đưa tới đảo đá quý lần nữa, nhưng bây giờ trên đảo chỉ còn \(N\) loại đá, loại thứ \(i\) còn đúng \(a_i\) viên, mỗi viên nặng \(w_i\) và có giá trị \(v_i\). Chiếc túi của chú chịu được tổng trọng lượng tối đa \(M\).

Hãy tìm tổng giá trị lớn nhất có thể mang về, biết rằng từ mỗi loại có thể lấy từ \(0\) đến \(a_i\) viên và tổng trọng lượng không vượt quá \(M\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(w_i\), \(v_i\), \(a_i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(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\)

Sample Input

3 7
2 5 3
3 8 1
1 2 4

Sample Output

18

Explanation

Chọn \(2\) viên loại 1 (nặng \(4\), giá trị \(10\)), \(1\) viên loại 2 (nặng \(3\), giá trị \(8\)): tổng nặng \(7\), giá trị \(18\). Có thể thay bằng \(3\) viên loại 1 và \(1\) viên loại 3 (nặng \(7\), giá trị \(17\)) nhưng kém hơn.