Dãy con

Trí tuệ nhân tạo của công ty AI Cơm Gà vừa phát hiện ra một thuật toán có thể chọn ra một dãy con cực kỳ hiệu quả để tiêu hóa dữ liệu. Để kiểm nghiệm khả năng đó, bạn được giao một nhiệm vụ sau:

Bạn có một dãy số nguyên $a$ gồm $n$ phần tử. Ngoài ra, bạn còn có một số nguyên $m$. Nhiệm vụ của bạn là chọn ra một **dãy con** (không nhất thiết liên tiếp) các chỉ số $b_1, b_2, \ldots, b_k$ ($1 \le b_1 < b_2 < \ldots < b_k \le n$), sao cho:

\begincenter
\(( \sum_{i=1}^{k} a_{b_i} ) \bmod m\)
\endcenter

đạt giá trị lớn nhất có thể. Nói cách khác, chọn một dãy con sao cho giá trị số dư của tổng chia cho $m$ là lớn nhất. Lưu ý rằng bạn được phép không chọn phần tử nào (khi đó tổng bằng 0).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 40\), \(1 \le m \le 10^9\)) --- số lượng phần tử trong dãy và số chia lấy dư.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) --- các phần tử trong dãy.

Output

In ra một số nguyên --- giá trị lớn nhất có thể của:

\begincenter
\(( \sum_{i=1}^{k} a_{b_i} ) \bmod m\)
\endcenter

Example

4 4
5 2 4 1

3

3 20
199 41 299

19