Chọn báu vật (Treasure Selection)

Nguồn: Luogu

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ loại báu vật. Loại $i$ có giá trị $v_i$, trọng lượng $w_i$ và tối đa $m_i$ món. Xe có tải trọng tối đa $W$. Hãy chọn các món để tổng trọng lượng không vượt quá $W$ và tổng giá trị lớn nhất.

Input

Dòng đầu chứa $n,W$. $n$ dòng tiếp theo chứa $v_i,w_i,m_i$.

Output

In tổng giá trị lớn nhất.

Subtask

• Subtask 1 (30%): $\sum m_i \le 10^4$, $W \le 10^3$, $v_i,w_i \le 100$.
• Subtask 2 (30%): $n \le 60$, $\sum m_i \le 5\cdot 10^4$, $W \le 10^4$.
• Subtask 3 (40%): $n \le 100$, $\sum m_i \le 10^5$, $W \le 4\cdot 10^4$, $v_i,w_i \le 1000$.

Toàn bộ dữ liệu tuân theo: $1 \le n \le 100$, $0 \le W \le 4\cdot10^4$, $1 \le v_i,w_i \le 1000$, $m_i\ge1$, $\sum m_i\le10^5$.

Ví dụ

Input

4 20
3 9 3
5 9 1
9 4 2
8 1 3

Output

47

Giải thích

Một lựa chọn tối ưu tôn trọng tải trọng $20$ cho tổng giá trị $47$.