Practice on Toph

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

OverloadedOsim

By rifat_072 · Limits 1s, 512 MB

$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.

  1. Let’s say, a group $a_1,a_2,...,a_r$ will be formed
  2. Now, Calculate, $sum = \sum_{i=1}^{r} a_i$
  3. Let, $k = sum \%x$
  4. 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.
  5. The current group cost is $\sum_{i=1}^{r} a_i$
  6. Remove $a_1,a_2,...,a_r$
  7. 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?

Input

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$.

Output

In a single line, output the maximum possible value.

Sample

InputOutput
5 10
3 4 2 4 5
39

Explanation
Suppose $1^{st}$ group will be formed index $1$ to index $2$, Then $a_1 + a_2 = 7$. Now, $k = 7\%10 = 7$. So, array $a$ will be $\{3 + 7 , 4 - 7, 2 + 7, 4 - 7, 5 + 7\} = \{10, -3, 9, -3, 12\}$. The first group cost will be $10 - 3 = 7$.

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$


    Discussion

    Statistics


    33% Solution Ratio

    serotoninEarliest, 2w ago

    AungkurFastest, 0.0s

    serotoninLightest, 131 kB

    serotoninShortest, 999B

    Submit

    Login to submit