Gộp để chia hết cho K

Cho dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) và một số nguyên \(K\). Một thao tác gộp chọn hai phần tử bất kỳ của dãy, xoá cả hai và thay bằng một phần tử mới có giá trị bằng tổng của chúng (vị trí đặt phần tử mới không quan trọng).

Sau khi thực hiện một số lượng tuỳ ý các thao tác gộp (có thể không thực hiện thao tác nào), hãy tìm số lượng lớn nhất các phần tử của dãy chia hết cho \(K\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, \dots, A_N\).

Output

• Một số nguyên duy nhất: số phần tử chia hết cho \(K\) nhiều nhất có thể đạt được.

Constraints

• \(1 \le N \le 10^5\)
• \(K \in \{4, 5\}\)
• \(1 \le A_i < 10^6\)

Phân bố điểm:

• \(30\%\) số test: \(N \le 10^3\), \(K = 4\).
• \(30\%\) số test: \(N \le 10^3\), \(K = 5\).
• \(40\%\) số test: \(N \le 10^5\), \(K = 4\) hoặc \(K = 5\).

Sample Input

7 4
5 6 7 9 2 3 10

Sample Output

3

Explanation

Số dư khi chia cho \(4\) lần lượt là \(1, 2, 3, 1, 2, 3, 2\). Gộp \(5+7=12\), \(9+3=12\), \(6+2=8\); dãy còn \(12, 12, 8, 10\) có \(3\) phần tử chia hết cho \(4\). Không thể đạt \(4\).