Tèo có một mảng ~a~ gồm ~n~ số nguyên, và một số nguyên đặc biệt ~m~.

Tèo cần chọn ra một dãy các chỉ số ~b_1, b_2, \ldots, b_k~ ~(1 \leq b_1 < b_2 < \ldots < b_k \leq n)~ sao cho giá trị của ~\sum_{i=1}^k a_{b_i} \mod m~ là lớn nhất có thể. Dãy được chọn có thể rỗng.

Hãy giúp Tèo tìm ra giá trị lớn nhất đó.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \leq 35, 1 \leq m \leq 10^9)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \leq a_i \leq 10^9)~.

Output

In ra giá trị lớn nhất có thể của ~\sum_{i=1}^k a_{b_i} \mod m~ mà Tèo có thể đạt được.

Ràng buộc

• ~25\%~ số test ứng với ~25\%~ số điểm có ~n \leq 20~.
• ~75\%~ số test còn lại không có ràng buộc gì thêm.

Sample Test

Input 1

5 10
47 16 9 2 56

Output 1

9

Input 2

4 8
9 2 5 4

Output 2

7