One day friend A went to his friend B's house and found N balls lying around, each with a value A[i] written on it. Being the ball lover that he was, he decided to put them all in a bucket.
But just as he was about to have some bucket-filling fun, B appeared out of nowhere like a math-loving superhero and said, "Hold up, boy! I'll buy you anything you want if you let me put some math into this party."
Confused but intrigued, A listened as B explained that if the bucket is empty, he can put a ball in it for free. But if it's not empty, he has to pick one ball from inside the bucket and another from outside and put them both in. The cost of doing this is GCD(a[i],a[j]).
Then A asked what GCD meant, and B chuckled and gave him a quick lesson. "It's the biggest number that can divide both those values evenly," he said.
A's eyes lit up at the possibility of getting some sweet swag from his friend. He wanted to maximize the total cost. So, how much cost did he end up getting?
Input format
- The first line contains an integer N.
- The second line contains N space-separated integers denoting the elements of array A.
Output format
Print the maximum total cost in a new line.
Constraints
1≤N,Ai≤105
Here the optimal solution is add 1st ball into the basket, then take 1st ball from inside basket , 2nd ball from outside the basket and put both inside the basket. The cost for this operation is GCD(4,6)=2. Pick 2nd ball from the basket, 3rd ball from outside and add both into the basket which cost GCD(6,9). The total cost is 3+2=5.
