Xếp hàng lên xe

Một kho hàng có $N$ loại hàng. Mỗi chiếc hàng loại $i$ nặng $w_i$ và có giá trị $v_i$; trong kho có $c_i$ chiếc hàng loại $i$. Chiếc xe tải chở được tổng khối lượng không quá $W$.

Yêu cầu: Hãy chọn các chiếc hàng xếp lên xe (mỗi loại $i$ chọn từ $0$ đến $c_i$ chiếc) sao cho tổng khối lượng không vượt quá $W$ và tổng giá trị là lớn nhất.

Dữ liệu vào

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

Dữ liệu ra

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

Ràng buộc

• $1\le N\le 1000$; $1\le W\le {10}^5$.
• $1\le w_i\le {10}^5$; $1\le v_i\le {10}^9$; $1\le c_i\le {10}^5$.

Subtasks

• Subtask 1 ($15\%$ số điểm): $N\le 10$, $W\le 100$ và $c_i\le 10$ với mọi $i$.
• Subtask 2 ($15\%$ số điểm): $c_i=1$ với mọi $i$.
• Subtask 3 ($20\%$ số điểm): $c_i\le 10$ với mọi $i$.
• Subtask 4 ($20\%$ số điểm): $N\le 100$.
• Subtask 5 ($30\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ