Yet Another Contest 2 P4 - No More Arithmetic

Points: 15 (partial)

Time limit: 2.0s

Python 5.0s

Memory limit: 512M

Author:

Problem types

Mike is tired of performing arithmetic with squares, so he has decided to break his square up into an array $A$ $A$ with $N$ $N$ integers. Furthermore, Mike wants to reduce the size of his array, so he will continue to perform the following process, in order, until he is unable to.

Select two integers $A_i$ $A_{i}$ and $A_j$ $A_{j}$ in the array such that $A_i \ge A_j$ $A_{i} \geq A_{j}$ and $i \ne j$ $i \neq j$ .
Select one of the four operations:
- $A_i + A_j$ $A_{i} + A_{j}$
- $A_i - A_j$ $A_{i} - A_{j}$
- $A_i \times A_j$ $A_{i} \times A_{j}$
- $A_i \div A_j$ $A_{i} \div A_{j}$ . Mike may only select this operation if the result is an integer.
Increase the total score by the number obtained from performing the selected operation taken modulo $M$ $M$ .
Remove either $A_i$ $A_{i}$ or $A_j$ $A_{j}$ from the array.

Your job is to help Mike find the maximum possible total score that can be obtained.

Constraints

$1 \le N \le 2\,000$ $1 \leq N \leq 2 000$

$1 \le M, A_i \le 10^9$ $1 \leq M, A_{i} \leq 10^{9}$

$M$ $M$ is a prime number.

Subtask 1 [10%]

$1 \le N \le 8$ $1 \leq N \leq 8$

Subtask 2 [20%]

$1 \le N \le 18$ $1 \leq N \leq 18$

Note that the previous subtask must be passed for this subtask to be evaluated.

Subtask 3 [20%]

$M = 2$ $M = 2$

Every element of $A$ $A$ can be expressed in the form $2^p \times 3^q$ $2^{p} \times 3^{q}$ , where $p$ $p$ and $q$ $q$ are non-negative integers.

Subtask 4 [Up to 50%]

No additional constraints.

In order to obtain all $50\%$ $50 %$ of the points allocated to this subtask, your submission must adhere to the following memory limits:

In Python, your program must not exceed $16$ $16$ MB of memory usage. Python users are recommended to use Python 2/3 over PyPy 2/3 when submitting.
In Java, your program must not exceed $64$ $64$ MB of memory usage.
In all other languages, your program must not exceed $8$ $8$ MB of memory usage.

If your program produces the correct output on all test cases but does not adhere to the memory limits listed above, then it will only receive $20\%$ $20 %$ out of the $50\%$ $50 %$ of points available for this subtask.

Note that the memory constraints listed above only apply to this subtask.

Note that all previous subtasks must be passed for this subtask to be evaluated.

Input Specification

The first line contains two integers $N$ $N$ and $M$ $M$ .

The next line contains $A_1, A_2, \dots, A_N$ $A_{1}, A_{2}, \dots, A_{N}$ .

Output Specification

On a single line, print the maximum possible score.

Sample Input 1

Copy

3 5
8 4 5

Sample Output 1

Copy

Explanation for Sample Output 1

Mike can first select $A_i = 8$ $A_{i} = 8$ and $A_j = 4$ $A_{j} = 4$ . Then, he will choose the $-$ $-$ operation and add $(8-4) \bmod 5 = 4$ $(8 - 4) mod 5 = 4$ to the total score. Then, he will remove $8$ $8$ from the array, so the array becomes $[4, 5]$ $[4, 5]$ .

Next, Mike selects $A_i = 5$ $A_{i} = 5$ and $A_j = 4$ $A_{j} = 4$ . Then, he will choose the $+$ $+$ operation and add $(5+4) \bmod 5 = 4$ $(5 + 4) mod 5 = 4$ to the total score. Then, he will remove $4$ $4$ from the array, so the array becomes $[5]$ $[5]$ .

Now, the array only consists of one integer. Mike is unable to perform any more moves, and his final score is $4+4 = 8$ $4 + 4 = 8$ . It can be shown that this is the maximal score.

Sample Input 2

Copy

4 2
1 1 1 1

Sample Output 2

Copy

Explanation for Sample Output 2

Since all elements in the array are equal, the choice of integers which Mike selects and deletes does not matter. Each time, he will choose the $\times$ $\times$ or $\div$ $\div$ operation and add $1$ $1$ to his total score, resulting in a final score of $3$ $3$ .

Sample Input 3

Copy

4 7
5 11 42 7

Sample Output 3

Copy

Sample Input 4

Copy

5 13
6 432 209 420 9

Sample Output 4

Copy

Comments

There are no comments at the moment.