Maximum Multiple

Given a sequence of N natural numbers and a positive natural number M, the task is to find the maximum multiple of M that can be obtained as the sum of any consecutive terms in the sequence.

Input:

The first line of input will contain exactly two natural numbers separated by a single space: the number N of elements in the sequence and the number M. The second line of input will contain N integers, separated pairwise by a single space. Consider that the sum of all terms in the sequence will not exceed 1.000.000.000.

Output:

The output should consist of a single line containing exactly one integer, the desired maximum multiple.

Note: All data is read from standard input and printed to standard output.

Constraints:

• For subtasks worth 20% of total score, it holds:
  1 ~\le~ N ~\le~ 1000, 1 ~\le~ M ~\le~ 10000
• For subtasks worth 40% of total score, it holds:
  1 ~\le~ N ~\le~ 10000, 1 ~\le~ M ~\le~ 100000
• For subtasks worth 100% of total score, it holds:
  1 ~\le~ N ~\le~ 1000000, 1 ~\le~ M ~\le~ 1000000

Example of Input 1:

8 7
1 2 3 4 5 6 7 8

Example of Output 1:

35

Example of Input 2:

5 17
6 4 3 7 1

Example of Output 2:

0

Explanation of the Examples:

In the first example, the sum of the terms 2+3+4+5+6+7+8 = 35 is the largest multiple of 7 that can be written as the sum of consecutive terms in the sequence.

In the second example, no non-zero sum of consecutive terms in the sequence is a multiple of 17. However, if we choose to sum zero terms of the sequence, resulting in a sum of zero, this is a multiple of 17 and is the maximum possible.