Ba Lô Có Giới Hạn Số Lượng

Cho $N$ loại vật. Loại vật thứ $i$ có khối lượng $w_i$, giá trị $v_i$, và số lượng có sẵn là $c_i$ (bạn chỉ được lấy tối đa $c_i$ vật loại $i$). Bạn có một chiếc ba lô sức chứa $W$.

Hãy tìm tổng giá trị lớn nhất có thể nhét vào ba lô.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
• $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $w_i$, $v_i$, $c_i$.

Dữ liệu ra

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

Ràng buộc

• $1\le N\le 100$
• $1\le W\le {10}^4$
• $1\le w_i\le W$
• $1\le v_i\le {10}^9$
• $1\le c_i\le 100$

Ví dụ

Ghi chú

Bài này khác với ba lô không giới hạn (mỗi loại có thể lấy vô hạn) và ba lô 0/1 (mỗi loại chỉ $1$ bản sao). Giới hạn $c_i$ là số hữu hạn nhưng có thể lớn.