Prefix - 3
Problem
Given a sequence of
N natural numbers. Find the maximum sum of all elements of a sequence's own prefix whose sum of all elements of the prefix, when divided by
K , has the same remainder as the sum of all elements of the given sequence. It is guaranteed that such a prefix exists.
Input
The first line contains two numbers: the number of numbers in the sequence
N (1 <= N <= 10
8) and the number
K ( 1 <= K <= 100). Next comes
N lines, one natural number per line. Each number does not exceed
10000.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
5 3
33
41
18
23
40 |
92 |