Bài toán cái túi 0/1 bằng phương pháp nhánh cận hoặc quay lui: Cho \(N\) đồ vật với trọng lượng w_i và giá trị v_i. Ba lô có tải trọng tối đa \(W\). Tìm giá trị lớn nhất có thể đạt được.

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

• Dòng 1: \(N, W\) (\(1 \le N \le 25, 1 \le W \le 10^9\)).
• \(N\) dòng tiếp theo: mỗi dòng gồm \(w_i, v_i\) (\(1 \le w_i, v_i \le 10^9\)).

Định dạng đầu ra

• Tổng giá trị cực đại tìm được.

Ví dụ

Input:

3 10
4 20
5 30
7 40

Output:

50

Giải thích: Chọn món 1 và món 2 có tổng trọng lượng \(4 + 5 = 9 \le 10\) và tổng giá trị \(20 + 30 = 50\).

Ràng buộc & Subtasks