$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.
$a_1,a_2,...,a_r$
will be formed$sum = \sum_{i=1}^{r} a_i$
$k = sum \%x$
$a_1 = a_1 + k$
, $a_2 = a_2 - k$
, $a_3 = a_3 + k$
, $a_4 = a_4 - k$
and so on.$\sum_{i=1}^{r} a_i$
$a_1,a_2,...,a_r$
$a$
is emptyYou 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 |
Explanation Then the array Suppose Then the array Now, the Then the array is empty. And the summation of all the three group cost is, |