Cái túi 3

Có \(n\) loại món đồ, món đồ loại thứ \(i\) có cân nặng \(w_i\), giá trị \(v_i\) và số lượng \(a_i\). Bạn có thể chọn số lượng món đồ tùy ý (không vượt quá số lượng có sẵn của mỗi loại), miễn tổng cân nặng không vượt quá \(S\). Hãy tìm cách chọn đồ để có được tổng giá trị lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, S\) (\(1 \le n \le 100\), \(1 \le S \le 10^4\)).

• Mỗi dòng trong \(n\) dòng tiếp theo gồm ba số nguyên \(w_i, v_i, a_i\) (\(1 \le w_i, v_i, a_i \le 10^4\)) --- cân nặng, giá trị và số lượng của món đồ loại thứ \(i\).

Output

In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.

Example

Input:

3 4
1 4 2
2 7 2
3 6 1

Output:

15

Note

Trong ví dụ trên, chọn 2 món đồ loại 1 (cân nặng \(1\times2=2\), giá trị \(4\times2=8\)) và 1 món đồ loại 2 (cân nặng \(2\), giá trị \(7\)), tổng cân nặng là \(4 \le S=4\) và tổng giá trị là \(8+7=15\), đây là phương án tối ưu.