Tý có một chiếc ba lô có tải trọng tối đa là \(W\). Có N món đồ trong cửa hàng, món đồ thứ i có trọng lượng là w_i và giá trị là \(v_i\).

Hãy chọn một tập hợp các món đồ để cho vào ba lô sao cho tổng trọng lượng không vượt quá \(W\) và tổng giá trị đạt được là lớn nhất.

Định dạng đầu vào

• Dòng thứ nhất chứa hai số nguyên \(N\) và W (\(1 \le N \le 50, 1 \le W \le 10^4\)).
• \(N\) dòng tiếp theo, dòng thứ i chứa hai số nguyên w_i và v_i (\(1 \le w_i \le 100, 1 \le v_i \le 10^3\)) lần lượt là trọng lượng và giá trị của món đồ thứ \(i\).

Định dạng đầu ra

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

Ví dụ

Input:

4 10
5 10
4 40
6 30
3 50

Output:

90

Giải thích: Chọn món đồ thứ 2 (\(w=4, v=40\)) và món đồ thứ 4 (\(w=3, v=50\)). Tổng trọng lượng là \(4 + 3 = 7 \le 10\), tổng giá trị là \(40 + 50 = 90\).

Ràng buộc & Subtasks