### Indian National Olympiad in Informatics

### Online Programming Contest, 15-16 July 2006

### Advanced Division

Problem 1: Best Sums, *(R Shreevatsa, CMI)*

Given a sequence of positive integers *a*_{1},
*a*_{2}, …, *a*_{N}, and 1 ≤
*i* ≤ *j* ≤ *N*, the partial sum from
*i* to *j* is *a*_{i} +
*a*_{i+1} + … + *a*_{j}.

In this problem, you will be given such a sequence and two
integers *P* and *K*. Your task is to find the smallest
partial sum modulo *P* that is at least *K*.

For example, consider the following sequence of integers:

12 13 15 11 16 26 11

Here *N* = 7. Suppose *K* = 2 and *P* = 17.
Then, the answer is 2 because 11+16+26 = 53 and 53 mod 17 is 2. On
the other hand, if *K* = 0 the answer is 0 since 15 + 11 + 16 +
26 = 68 and 68 mod 17 is 0.

Input format

The first line contains three integers *N*, *K* and
*P*. This is followed by *N* lines each containing a
single integer.

Output format

A single integer indicating the minimum possible segment sum modulo
*P* that is at least *K*.

Test Data:

You may assume 1 ≤ *N* ≤ 100000.

Example:

Here is the sample input and output corresponding to the example above.

Sample Input

7 2 17
12
13
15
11
16
26
11

Sample Output

2