Problem Description

As everyone knows, student Xiaocong is good at calculations, especially at checking whether one number is a multiple of another. However, Xiaocong is only good at the case with two numbers, and becomes troubled when there are many numbers. Now Xiaocong gives you $n$ numbers and hopes that you can find three numbers among them such that the sum of these three numbers is a multiple of $K$, and this sum is as large as possible. The testdata guarantees that a solution always exists.

Input Format

Read input from standard input.

The first line contains $2$ positive integers, $n$ and $K$.

The second line contains $n$ positive integers, representing the given $n$ numbers.

Output Format

Output one line containing one integer, the required sum.

4 3
1 2 3 4

9

Hint

Sample Explanation

Choose $2$, $3$, and $4$.

Constraints

For $30\%$ of the testdata, $n \le 100$.

For $60\%$ of the testdata, $n \le 1000$.

For the other $20\%$ of the testdata, $K \le 10$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le K \le 10^3$, and each of the given $n$ numbers does not exceed $10^8$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2018, 9th Provincial Contest.

Translated by ChatGPT 5