Tập con lớn nhất có tổng chia hết

Cho \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) và một số nguyên dương \(K\). Hãy chọn ra một số phần tử (theo vị trí, không cần các giá trị khác nhau) sao cho tổng các phần tử được chọn chia hết cho \(K\) và số phần tử được chọn là nhiều nhất có thể. In ra số phần tử đó.

Tập rỗng có tổng bằng \(0\) (chia hết cho mọi \(K\)), nên nếu không thể chọn được tập khác rỗng nào thì đáp án là \(0\).

Input

• Dòng đầu gồm hai số nguyên dương \(n\) và \(K\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\).

Output

In ra một số nguyên là số phần tử lớn nhất của một tập con có tổng chia hết cho \(K\).

Constraints

• \(1 \le n \le 22\), \(1 \le K \le 2 \cdot 10^{10}\)
• \(1 \le A_i \le 10^9\)

Sample Input

6 5
3 8 4 7 6 1

Sample Output

5

Explanation

Tổng cả sáu số là \(29\) không chia hết cho \(5\). Bỏ số \(4\) được tập gồm \(5\) số \(\{3, 8, 7, 6, 1\}\) có tổng \(25\) chia hết cho \(5\). Không thể chọn cả \(6\) số nên đáp án là \(5\).