An có một chiếc túi chịu được tối đa trọng lượng W. Có N món đồ, mỗi món đồ i có trọng lượng \(w_i\) và giá trị \(v_i\). Hãy chọn một số món đồ bỏ vào túi sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất.

Với \(N \le 40\), thuật toán quy hoạch động thông thường O(\(N\timesW\)) không khả thi. Sử dụng Meet in the Middle:

1. Chia đồ làm 2 nửa, sinh tất cả tổ hợp (trọng lượng, giá trị) của mỗi nửa.
2. Sắp xếp nửa thứ hai theo trọng lượng, loại bỏ các tổ hợp bị trội (cả trọng lượng lớn hơn và giá trị nhỏ hơn).
3. Với mỗi tổ hợp ở nửa đầu, dùng binary search tìm tổ hợp tốt nhất ở nửa thứ hai.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N (\(1 \le N \le 40\)) và W (\(1 \le W \le 10^18\)).
• N dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i\) (\(1 \le w_i \le 10^9\)) và v_i (\(1 \le v_i \le 10^9\)).

Đầu ra

Một số nguyên là tổng giá trị lớn nhất.

Ví dụ

Input:
4 10
5 10
3 7
2 5
4 8

Output:
22

Giải thích

Chọn đồ 1 \((5, 10)\), đồ 2 \((3, 7)\), đồ 3 \((2, 5)\): tổng trọng 10, tổng giá trị 22.

Ràng buộc & Subtasks