Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

$NullNoman$ is a good boy. He loves programming and array very much. In this quarantine, he solves programming problems on different online judges all the time. Sometimes $NullNoman$ annoys his friends by asking them to solve some hard problems. For this reason, his friends don’t like him very much.

One day his friend $PointerPias$ came to his house for a visit. $NullNoman$ became very happy and immediately started discussing a very hard problem of arrays with $PointerPias$. Soon $PointerPias$ felt uncomfortable. He broke into tears as he couldn’t bear the pain. After some time $PointerPias$ ran away from $NullNoman’s$ home.

This isn’t a big deal for you. But you are invited to $NullNoman’s$ upcoming birthday party next week. Where he may annoy you by discussing the same problem. It is better to practice it beforehand. Let’s take a look at the problem on which $PointerPias$ cried.

You will be given an array $a$ of size $n$. You have to group the array in a specific manner. A group must be formed in sequential order. After selecting a group, the array must be updated before calculating the group cost.

- Let's say, a group $a_1,a_2,...,a_r$ will be formed
- Now, Calculate, $sum = \sum_{i=1}^{r} a_i$
- Let, $k = sum \%x$
- Update the array, like, $a_1 = a_1 + k$, $a_2 = a_2 - k$, $a_3 = a_3 + k$, $a_4 = a_4 - k$ and so on.
- The current group cost is $\sum_{i=1}^{r} a_i$
- Remove $a_1,a_2,...,a_r$
- Then form another group from the new array until the array $a$ is empty

You have to maximize the summation of the costs of all groups you have formed . What do you think, can you solve it?

The first line of the input contains two integers $n$ $(1 \leq n \leq 100)$, denoting the length of the array and $x$ $(1 \leq x \leq 10)$, denoting the magical value.

The second line contains $n$ integers $a_1,a_2,...,a_n$ $(-10^{9} ≤ a_i ≤ 10^{9})$, where $a_i$ is the $i^{th}$ element of array $a$.

In a single line, output the maximum possible value.

Input | Output |
---|---|

5 10 3 4 2 4 5 | 39 |

Then the array $a$ become: $\{9, -3, 12\}$ Suppose $2^{nd}$ group will be formed index $1$ to index $2$, Then $a_1 + a_2 = 6$. Now, $k = 6\%10 = 6$. So, array $a$ will be $\{9 + 6 , -3 - 6, 12 + 6\} = \{15, -9, 18\}$. The second group cost will be $15 - 9 = 6$. Then the array $a$ become: $\{18\}$ Now, the $3^{rd}$ group will be formed index 1 to index 1. Now, $k = 18 \% 10 = 8$. So, array $a$ will be $\{18 + 8\} = \{26\}$. The third group cost will be $26$. Then the array is empty. And the summation of all the three group cost is, $7 + 6 + 26 = 39$ |

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.