Tập con dài nhất 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 một tập con của các phần tử (mỗi phần tử dùng nhiều nhất một lần) có tổng chia hết cho \(K\) và có số phần tử nhiều nhất. Nếu không tồn tại tập con khác rỗng nào thỏa mãn thì in \(0\).

Input

• Dòng đầu: hai số nguyên \(n\) và \(K\).
• Dòng thứ hai: \(n\) số nguyên \(A_1, \dots, A_n\).

Output

• In ra 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 K \le 4 \times 10^{10}\), \(1 \le A_i \le 10^9\)
• Subtask 1: \(1 \le n \le 20\)
• Subtask 2: \(21 \le n \le 40\)

Sample Input

6 5
3 7 2 8 4 1

Sample Output

6

Explanation

Tổng cả sáu số là \(25\), chia hết cho \(5\).