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

NullNomanNullNoman 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 NullNomanNullNoman 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 PointerPiasPointerPias came to his house for a visit. NullNomanNullNoman became very happy and immediately started discussing a very hard problem of arrays with PointerPiasPointerPias. Soon PointerPiasPointerPias felt uncomfortable. He broke into tears as he couldn’t bear the pain. After some time PointerPiasPointerPias ran away from NullNomansNullNoman’s home.

This isn’t a big deal for you. But you are invited to NullNomansNullNoman’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 PointerPiasPointerPias cried.

You will be given an array aa of size nn. 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 a1,a2,...,ara_1,a_2,...,a_r will be formed
  2. Now, Calculate, sum=i=1raisum = \sum_{i=1}^{r} a_i
  3. Let, k=sum%xk = sum \%x
  4. Update the array, like, a1=a1+ka_1 = a_1 + k, a2=a2ka_2 = a_2 - k, a3=a3+ka_3 = a_3 + k, a4=a4ka_4 = a_4 - k and so on.
  5. The current group cost is i=1rai\sum_{i=1}^{r} a_i
  6. Remove a1,a2,...,ara_1,a_2,...,a_r
  7. Then form another group from the new array until the array aa 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 nn (1n100)(1 \leq n \leq 100), denoting the length of the array and xx (1x10)(1 \leq x \leq 10), denoting the magical value.
The second line contains nn integers a1,a2,...,ana_1,a_2,...,a_n (109ai109)(-10^{9} ≤ a_i ≤ 10^{9}), where aia_i is the ithi^{th} element of array aa.

Output

In a single line, output the maximum possible value.

Sample

InputOutput
5 10
3 4 2 4 5
39

Explanation
Suppose 1st1^{st} group will be formed index 11 to index 22, Then a1+a2=7a_1 + a_2 = 7. Now, k=7%10=7k = 7\%10 = 7. So, array aa will be {3+7,47,2+7,47,5+7}={10,3,9,3,12}\{3 + 7 , 4 - 7, 2 + 7, 4 - 7, 5 + 7\} = \{10, -3, 9, -3, 12\}. The first group cost will be 103=710 - 3 = 7.

Then the array aa become: {9,3,12}\{9, -3, 12\}

Suppose 2nd2^{nd} group will be formed index 11 to index 22, Then a1+a2=6a_1 + a_2 = 6. Now, k=6%10=6k = 6\%10 = 6. So, array aa will be {9+6,36,12+6}={15,9,18}\{9 + 6 , -3 - 6, 12 + 6\} = \{15, -9, 18\}. The second group cost will be 159=615 - 9 = 6.

Then the array aa become: {18}\{18\}

Now, the 3rd3^{rd} group will be formed index 1 to index 1. Now, k=18%10=8k = 18 \% 10 = 8. So, array aa will be {18+8}={26}\{18 + 8\} = \{26\}. The third group cost will be 2626.

Then the array is empty. And the summation of all the three group cost is, 7+6+26=397 + 6 + 26 = 39


Discussion

Statistics


33% Solution Ratio

serotoninEarliest, Jul '20

AungkurFastest, 0.0s

serotoninLightest, 131 kB

serotoninShortest, 999B

Submit

Login to submit

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