Phần Dư Tập Con Lớn Nhất · canuc80k1021

Cho dãy $a_{1}, a_{2}, \dots, a_{n}$ và số nguyên dương $m$ . Bạn được chọn một tập con bất kỳ các vị trí trong dãy; tập con rỗng cũng được phép. Gọi $S$ là tổng các phần tử tại những vị trí đã chọn. Hãy tìm giá trị lớn nhất có thể của $S$ $mod$ $m$ , trong đó kết quả modulo luôn thuộc đoạn từ $0$ đến $m - 1$ .

Input

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In một số nguyên duy nhất - phần dư lớn nhất có thể nhận được.

Constraints

$1 \leq n \leq 35$ .
$1 \leq m \leq 1 0^{9}$ .
$1 \leq a_{i} \leq 1 0^{9}$ .
Tập con được phép rỗng.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 20$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4 10
6 7 4 2

Output

Giải thích: Chọn các vị trí chứa $7$ và $2$ . Tổng bằng $9$ , nên phần dư modulo $10$ là $9$ ; không phần dư nào có thể lớn hơn $9$ .

Phân tích: Với n≤35, duyệt 2^n tập con là quá lớn, còn quy hoạch theo modulo không phù hợp khi m tới 10^9. Chia dãy thành hai nửa và sinh mọi phần dư tập con của mỗi nửa. Mọi tập con toàn dãy tương ứng với một phần dư x bên trái và y bên phải.
Thuật toán: Sinh hai danh sách phần dư L và R, mỗi danh sách luôn chứa 0 ứng với tập rỗng. Sắp xếp R. Với mỗi x trong L, dùng upper_bound để tìm phần tử lớn nhất y≤m-1-x, rồi cập nhật x+y. Không cần xét riêng cặp có x+y≥m: phần dư khi đó là x+y-m, nhỏ hơn cả x lẫn y, trong khi x và y riêng lẻ đều đã là các phương án hợp lệ nhờ tập rỗng ở nửa còn lại.
Chứng minh: Mọi tập con của dãy được tách duy nhất thành tập con ở nửa trái và nửa phải, nên cặp phần dư của nó xuất hiện trong L×R. Nếu x+y<m, giá trị nhận được là x+y; với x cố định, phần tử lớn nhất của R không vượt m-1-x cho giá trị tốt nhất trong nhóm này, và thuật toán xét đúng phần tử đó. Nếu x+y≥m, phần dư x+y-m nhỏ hơn x và nhỏ hơn y; hai giá trị x và y đều có thể đạt bằng cách chọn tập con rỗng ở nửa kia, nên cặp bị tràn không thể cải thiện đáp án. Vì thế thuật toán xét một phương án ít nhất tốt bằng mọi tập con và kết quả cuối cùng là tối ưu.
Độ phức tạp: Thời gian O(2^(n/2)·log(2^(n/2))), bộ nhớ O(2^(n/2)).