Minimum Sum Divisible by k

You are given an array of n non‐negative integers and a positive integer k. You must modify exactly one element of the array by replacing it with another non‐negative integer such that the overall sum becomes divisible by k. However, if the sum is already divisible by k, you are allowed to perform an identity replacement (i.e. replace an element with itself).

Under the rules of the modification, it turns out that a valid change exists only if there is at least one element in the array that is divisible by k (that is, an element a[i] with a[i] mod k = 0). In this case:

• Let S be the original sum and r = S mod k.
• If r = 0, then the answer is S (using the identity replacement).
• If r ≠ 0 and there exists an element with a[i] mod k = 0, one can lower the overall sum by replacing that element appropriately so that the new sum becomes S − r which is divisible by k.

If no such element exists, then it is impossible to achieve a divisible sum by modifying exactly one element, and you should return -1.

The task is to compute the minimum possible new sum (which is S when no change is needed, or S − r when a valid change exists) or output -1 if the modification is impossible.

Note: Input integers are non‐negative and the replacement number must also be non‐negative.

inputFormat

The first line contains two space-separated integers n and k — the number of elements in the array and the divisor respectively. The second line contains n space-separated non-negative integers representing the array.

outputFormat

Output a single integer: the minimum possible new sum after modifying exactly one element so that the sum is divisible by k, or -1 if it is not possible.## sample

3 3
1 2 3

6