Description

jyy has always wanted to return to Earth as soon as possible, but unfortunately his spaceship does not have enough fuel. One day he went to ask the Martians for fuel again. This time the Martians agreed, asking jyy to trade with the bottles on his spaceship. There are $N$ bottles on jyy's spaceship ($1 \leq N \leq 1000$), and after negotiation, the Martians only want $K$ of them.

After jyy gives $K$ bottles to the Martians, they use them to fill some fuel for jyy. None of the bottles have graduation marks; only the capacity is labeled at the mouth. The capacity of the $i$-th bottle is $V _ i$ ($V _ i$ is an integer and satisfies $1 \leq V _ i \leq 10 ^ 9$). The Martians are stingy and will not fill all bottles to the brim. After they take the bottles, they will fiddle around in the fuel depot and produce a tiny amount of fuel just to get by. jyy certainly knows this trick, so he learned in advance exactly what the Martians do.

In the fuel depot, the Martians only perform the following $3$ types of operations:

1. Fill some bottle completely with fuel;
2. Pour all the fuel in some bottle back into the depot;
3. Pour fuel from bottle $a$ into bottle $b$ until bottle $b$ is full or bottle $a$ is empty. Loss during the pouring process can be ignored.

The fuel they hand over is, of course, the smallest positive volume obtainable by these operations. jyy knows that for different choices of bottles, the Martians might be forced to give different volumes of fuel. jyy wants to find the optimal set of bottles so that the Martians are forced to give as much fuel as possible.

Input Format

The first line contains two integers $N, K$. The next $N$ lines each contain one integer; the integer on the $(i+1)$-th line is $V _ i$.

Output Format

Output a single integer on one line, representing the maximum amount of fuel the Martians will be forced to give.

3 2
3
4
4

4

Hint

Choose the 2nd and 3rd bottles; the Martians will be forced to give a volume of 4.

Translated by ChatGPT 5