AT_tkppc4_2_h 打鍵戦争

现在已经从所有成员中选出了能力值最小的 $K$ 个成员作为代表候选人。 社团社长决定要按照如下规则进行操作： 社长可以进行 $0$ 次或多次操作； 每次操作中，社长可以任选两个成员 $i$ 和 $j$ 进行打键比赛；并且打键结果是 $i$ 获胜还是 $j$ 获胜是根据下面的概率决定的： 若成员 $i$ 能力值为 $A_i$，$j$ 能力值为 $A_j$，则 $i$ 获胜的概率为 $\frac{A_i}{A_i+A_j}$，$j$ 获胜的概率为 $\frac{A_j}{A_i+A_j}$； 当某次比赛中 $i$ 获胜时，什么都不会发生。 当某次比赛中 $j$ 获胜时，成员 $j$ 将成为新的代表候选人，成员 $i$ 将从原先的代表候选人中删除。 社长可以在任何时候停止操作。此时成为代表选手的就是最后留下的所有代表候选人。 社长希望能够通过尽量少的操作次数，使得留下的代表选手的能力值之和最大化。在操作次数期望值最小的前提下，求出最终的代表选手的能力值之和。

从标准输入读入数据。输入的第一行有两个正整数 $N$ 和 $K$，含义如上。接下来的 $N$ 行，每行对应着每个成员的能力值。

输出到标准输出。输出共一行，即操作次数期望值的最小值。

### 制約 - 入力は全て整数である。 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ 2K\ \leq\ N $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ A_i\ \neq\ A_j(i\ \neq\ j) $