题目描述

Jack 来到他最喜欢的赌场，身上有 $1000$ 美元。赌场里除了唯一的一台老虎机之外，什么都没有。

Jack 知道这家赌场的历史。

很久以前，未来的赌场老板在散步时突然看到一个由 $n$ 个整数组成的数组

其中每个数都在 $0$ 到 $100$ 之间。他从中等概率随机选择一个下标 $i$，并决定建立一家只有一台老虎机的赌场，这台老虎机的中奖概率为

一旦下标 $i$ 被选定，它便永久固定。老虎机在之后的每一局中都使用同一个 $p_i$。

Jack 知道数组 $p_1,p_2,\ldots,p_n$，但不知道赌场老板当初选择了哪个下标。

每一局中，Jack 可以下注一个非负整数 $x$，然后拉动拉杆：

1. 以 $\frac{p_i}{100}$ 的概率中大奖。老虎机返还 $2x$ 美元，因此 Jack 净赚 $x$ 美元；
2. 以 $1-\frac{p_i}{100}$ 的概率遭遇厄运。老虎机不返还任何钱，因此 Jack 损失 $x$ 美元。

即使 Jack 下注 $0$ 美元，他仍然能够知道本局结果是中奖还是失败。

老虎机并不耐用，因此 Jack 最多只能玩 $k$ 局。

请计算 Jack 使用最优策略时能够获得的最大期望利润。利润定义为最终资金减去初始的 $1000$ 美元。

Jack 的下注额不能超过他当前拥有的资金。

输入格式

第一行包含两个整数 $n,k$：

• $n$ 表示候选概率的数量；
• $k$ 表示最多可以进行的局数。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$。

输出格式

输出一个实数，表示 Jack 使用最优策略时能够获得的最大期望利润。

若答案的绝对误差或相对误差不超过 $10^{-4}$，则认为答案正确。

样例 1

2 2
70 30

160

样例 2

2 30
30 70

12099716.1778528057038784

样例 3

2 5
40 50

0

样例 4

6 6
10 20 60 30 40 50

29.40799999999990177457221

样例 5

1 5
61

1702.708163199999489734182

数据范围