Mike is tired of performing arithmetic with squares, so he has decided to break his square up into an array with 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 and in the array such that and .
- Select one of the four operations:
- . 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 .
- Remove either or from the array.
Your job is to help Mike find the maximum possible total score that can be obtained.
is a prime number.
Subtask 1 [10%]
Subtask 2 [20%]
Note that the previous subtask must be passed for this subtask to be evaluated.
Subtask 3 [20%]
Every element of can be expressed in the form , where and are non-negative integers.
Subtask 4 [Up to 50%]
No additional constraints.
In order to obtain all of the points allocated to this subtask, your submission must adhere to the following memory limits:
- In Python, your program must not exceed 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 MB of memory usage.
- In all other languages, your program must not exceed 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 out of the 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.
The first line contains two integers and .
The next line contains .
On a single line, print the maximum possible score.
Sample Input 1
3 5 8 4 5
Sample Output 1
Explanation for Sample Output 1
Mike can first select and . Then, he will choose the operation and add to the total score. Then, he will remove from the array, so the array becomes .
Next, Mike selects and . Then, he will choose the operation and add to the total score. Then, he will remove from the array, so the array becomes .
Now, the array only consists of one integer. Mike is unable to perform any more moves, and his final score is . It can be shown that this is the maximal score.
Sample Input 2
4 2 1 1 1 1
Sample Output 2
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 or operation and add to his total score, resulting in a final score of .
Sample Input 3
4 7 5 11 42 7
Sample Output 3
Sample Input 4
5 13 6 432 209 420 9
Sample Output 4