Description

Jack 正在他最喜爱的赌场里，身上有 1000 美元。赌场里除了一台老虎机外一无所有。Jack 知道这家赌场的历史。从前，赌场未来的主人正在散步时，突然看到了一个包含 $n$ 个整数选项的数组 $p_1, \dots, p_n$，每个选项都在 0 到 100 之间。他均匀随机地选取了一个索引 $i$ ($1 \le i \le n$)，并认为创建一个只有一台老虎机的赌场是个好主意，这台老虎机的中奖概率为 $\frac{p_i}{100}$。于是他照做了。

Jack 知道主人散步时突然看到的选项数组 $p_1, \dots, p_n$，但他不知道主人具体选取了哪个 $i$。然而，被选中的索引 $i$ 是永久固定的；老虎机始终使用相同的 $p_i$，如下所述。

在老虎机上，Jack 可以下注 $x$ 美元，其中 $x$ 是一个 非负 整数，然后拉下拉杆。接着：

1. 以概率 $\frac{p_i}{100}$，它会中奖，老虎机返还给他 $2x$ 美元，因此他盈利 $x$ 美元。

2. 以概率 $1 - \frac{p_i}{100}$，它会失败，老虎机不返还任何钱，因此他亏损 $x$ 美元。

即使 Jack 下注 0 美元，他也能知道结果是失败还是中奖。

此外，老虎机不太耐用，因此 Jack 最多只能玩 $k$ 轮。

通过最优策略，找出 Jack 能获得的最大期望 利润。这里的利润定义为 Jack 最终拥有的金额减去他初始的 1000 美元。

当然，Jack 不能下注超过他当前余额的金额。

Input Format

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 100\,000$；$1 \le k \le 30$) —— 选项数量和轮数限制。第二行包含 $n$ 个整数 $p_1, \dots, p_n$ ($0 \le p_i \le 100$) —— 选项。

Output Format

输出一个实数 —— Jack 通过最优策略能获得的期望利润。如果你的答案的绝对误差或相对误差不超过 $10^{-4}$，即被视为正确。

2 2
70 30

160

2 30
30 70

12099716.1778528057038784

2 5
40 50

0

6 6
10 20 60 30 40 50

29.40799999999990177457221

1 5
61

1702.708163199999489734182