Cho mảng A gồm N số nguyên dương và số X. Hãy tìm tổng tập con gần với X nhất (không vượt quá X cũng được). Nếu có nhiều tổng cách X cùng một khoảng cách, chọn tổng lớn nhất.

Sử dụng Meet in the Middle: chia mảng làm 2 nửa, sinh tất cả tổng tập con của mỗi nửa, sắp xếp nửa thứ hai, dùng binary search để tìm tổng gần X nhất.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N (1 ≤ N ≤ 40) và X (1 ≤ X ≤ 10^18).
• Dòng thứ hai chứa N số nguyên dương A_i (1 ≤ A_i ≤ 10^15).

Đầu ra

Tổng tập con gần X nhất.

Ví dụ

Input:
5 20
2 3 5 8 13

Output:
21

Giải thích

Các tổng tập con: 2,3,5,8,10,11,13,15,16,18,21,... Tổng 21 gần 20 nhất (chênh 1).