Description

jyy就一直想著盡快回地球，可惜他飛船的燃料不夠了。 有一天他又去向火星人要燃料，這次火星人答應了，要jyy用飛船上的瓶子來換。jyy 的飛船上共有 N個瓶子(1<=N<=1000) ，經過協商，火星人只要其中的K 個 。 jyy 將 K個瓶子交給火星人之后，火星人用它們裝一些燃料給 jyy。所有的瓶子都沒有刻度，只在瓶口標注了容量，第i個瓶子的容量為Vi（Vi 為整數，并且滿足1<=Vi<=1000000000 ） 。 火星人比較吝嗇，他們并不會把所有的瓶子都裝滿燃料。他們拿到瓶子后，會跑到燃料庫里鼓搗一通，弄出一小點燃料來交差。jyy當然知道他們會來這一手，于是事先了解了火星人鼓搗的具體內容?；鹦侨嗽谌剂蠋炖镏粫鋈缦碌?種操作： 1、將某個瓶子裝滿燃料； 2、將某個瓶子中的燃料全部倒回燃料庫； 3、將燃料從瓶子a倒向瓶子b，直到瓶子b滿或者瓶子a空。燃料傾倒過程中的損耗可以忽略?；鹦侨四贸龅娜剂?，當然是這些操作能得到的最小正體積。 jyy知道，對于不同的瓶子組合，火星人可能會被迫給出不同體積的燃料。jyy希望找到最優的瓶子組合，使得火星人給出盡量多的燃料。

Input

第1行：2個整數N,K， 第2..N 行：每行1個整數，第i+1 行的整數為Vi

Output

僅1行，一個整數，表示火星人給出燃料的最大值。

Sample Input

3 2 3 4 4

Sample Output

4

HINT

選擇第2 個瓶子和第 個瓶子，火星人被迫會給出4 體積的容量。

題解

這題就是不斷地倒水，最后能得到的最小值一定是這k個數的最大公約數。（由裴蜀定理可知）

設a1,a2,a3……an為n個整數，d是它們的最大公約數，那么存在整數x1……xn使得x1*a1+x2*a2+…xn*an=d。 特別來說，如果a1…an互質（不是兩兩互質），那么存在整數x1……xn使得x1*a1+x2*a2+…xn*an=1。證法類似兩個數的情況。

所以找出n個數所有因數，從大到小第一個出現k次的即是答案。

代碼