MOG
Spanish
|
English

Matcom Online Grader

MOG Round #35

Ended

E - Equal distribution

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

Fito's family is organizing some candies they still have from last year's Halloween because they would rather make a deal with the kids than have them do a trick.


They have several types of candy and from each type, they have several candies. So the kids don't get angry they want to give the same amount of candy per type to each of them. However, depending on how many children there are, this may not be possible. That's why they decide to get rid of all candies of certain types, in order to be able to distribute the remaining candies between at least 2 children. Logically, there are several ways to do this but they want to eliminate in total as few candies as possible.

Your task is to write a program that tells Fito what is the maximum number of candies they can keep.

Input

The input consists of a single test. The first line contains an integer $N$ ($1 \leq N \leq 1000$) that represents the number of candy types. The $i+1$-th line (for $1 \leq i \leq N$) consists of an integer $c_i$ ($1 \leq c_i \leq 10^9$), which is the number of candies of the $i$-th type.

Output

Print the maximum number of candies Fito's family can keep, such that it is possible to distribute them between at least two kids.

Sample test(s)

Input
4 1 2 3 4
Output
6
Input
1 1
Output
0
Input
3 9 17 31
Output
31

Hints

In the first example, the family can remove the first and third types. Then they will keep $2 + 4=6$ candies. Both $2$ and $4$ can be equally distributed between at least $2$ kids.