Ba Lô Không Giới Hạn

Cho $N$ loại vật. Loại vật thứ $i$ có khối lượng $w_i$ và giá trị $v_i$. Bạn có một chiếc ba lô sức chứa $W$ (tổng khối lượng các vật đem theo không được vượt quá $W$).

Với mỗi loại vật, bạn được lấy số lượng không giới hạn (có thể lấy $0$, $1$, $2$, $\dots$ vật cùng loại). 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$ — số loại vật và sức chứa ba lô.
• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ và $v_i$ — khối lượng và giá trị của loại vật thứ $i$.

Dữ liệu ra

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

Ràng buộc

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

Ví dụ

Ghi chú

Với ví dụ $2$, chiến lược "chọn loại có tỷ số giá trị/khối lượng cao nhất" sẽ chọn loại $1$ (tỷ số $9/5=1.8>10/6\approx 1.67$), nhưng cách làm này không tối ưu vì để lại $2$ đơn vị khối lượng thừa.