In the fairy village with a river passing through the middle of the city, there is a fairy named Emma who wishes to fly higher into the sky. In order for that, she decides to borrow the power of pixie dusts, however; pixie dusts aren't for sale. So she has to make it herself by mixing the elements that she gets from the shop. In the shop, there are $$$M$$$ elements, and each of them has the cuteness level of $$$A[i]$$$. Each element has a $$$\textbf{distinct}$$$ cuteness level from others. However, Emma is allowed to purchase only $$$N$$$ elements (any elements).
Making pixie dust isn't an easy task. To make it, two elements have to be combined. Assuming those have cuteness levels of $$$X$$$ and $$$Y$$$, the result will be $$$\textbf{one}$$$ pixie dust and an element of cuteness level of $$$GCD(X, Y)$$$. (Note that this result element can be used to create another pixie dust again and again and those 2 initial elements will be $$$\textbf{gone}$$$)
Emma's goal is to get $$$K$$$ pixie dust to fly through the mist and cloud, together with maximizing the sum of the cuteness levels of every element left. Emma will be very pleased if you help her choose $$$N$$$ elements from the shop and tell her the maximum sum of the cuteness levels of every element left.
The first line contains three integers $$$M, N, K (1 \leq K \lt N \leq M \leq 5,000,000)$$$ — the number of elements sold in the shop, the number of elements that Emma can buy, the number of Pixie dust that Emma wants
The next line contains $$$M$$$ integers $$$A[1],A[2],A[3],...,A[M]$$$ $$$(1 \leq A[i] \leq 5,000,000)$$$ and $$$\textbf{all of them are distinct}$$$. — the cuteness level of each element sold in the shop
Output a single value — the largest sum of cuteness of all elements left after the procedure of making Pixie dust
7 4 211 1 3 2 7 8 12
13
8 6 214 11 2 4 9 12 8 13
42
In the first test case, Emma can choose elements from the shop with a cuteness level of $$$11,2,8,12$$$. First, combining elements with cuteness $$$2$$$ and $$$8$$$, Emma gets the first Pixie dust and element of cuteness $$$GCD(2,8)=2$$$. So, the elements left have a cuteness level of $$$11,12,2$$$. Then, combining elements with cuteness $$$2$$$ and $$$11$$$, Emma gets the second Pixie dust and element of cuteness $$$GCD(2,11)=1$$$. So, the elements left have a cuteness level of $$$12,1$$$. Thus, in this case, the sum is $$$12+1=13$$$, which is the largest sum Emma can achieve.
In the second test case, Emma can choose elements from the shop with a cuteness level of $$$14,11,4,12,8,13$$$. First, combining elements with cuteness $$$12$$$ and $$$8$$$, Emma gets the first Pixie dust and element of cuteness $$$GCD(12,8)=4$$$. So, the elements left have a cuteness level of $$$14,11,4,13,4$$$. Then, combining elements with cuteness $$$4$$$ and $$$4$$$, Emma gets the second Pixie dust and element of cuteness $$$GCD(4,4)=4$$$. So, the elements left have a cuteness level of $$$14,11,13,4$$$. Thus, in this case, the sum is $$$14+11+13+4=42$$$, which is the largest sum Emma can achieve.
| Name |
|---|


