问题陈述

我们正在开发世界上最酷的AI机器人产品。经过长时间的努力，我们终于将产品的修订版 $R\_{RC}$ 作为发布候选版本发送给了QA团队。然而，他们报告说一些测试失败了！由于我们太懒，没有设置持续集成系统，我们不知道软件何时出现故障。我们只知道软件在上一个修订版 $R\_{PASS}$ 中通过了所有测试。为了确定软件开始出现故障的修订版 $R\_{ENBUG}$ （$R\_{PASS} \\lt R\_{ENBUG} \\le R\_{RC}$），我们必须逐个修订版地测试我们的产品。

在这里，我们可以假设以下条件：

• 当我们在修订版 $R$ 上进行测试时，如果 $R \\lt R\_{ENBUG}$，则测试通过，否则测试失败。
• 在 $R\_{PASS} + 1$ 和 $R\_{RC}$ 之间的修订版中，$R\_{ENBUG}$ 是等可能的。

根据第一个假设，我们不需要测试所有的修订版。我们只需要找到修订版 $R$，使得在 $R - 1$ 的测试通过，并且在 $R$ 的测试失败。我们有 $K$ 个测试设备。使用它们，我们最多可以同时测试 $K$ 个不同的修订版。我们称之为 "并行测试"。由于测试环境的限制，即使我们不使用所有的 $K$ 个设备，我们也不能在当前并行测试完成之前开始新的测试。

并行测试会有一些成本。测试失败越多，并行测试的成本就越高。如果在一个并行测试中有 $i$ 个测试失败，则其成本为 $T\_i$（$0 \\le i \\le K$）。如果我们运行多次并行测试，则总成本是它们成本的总和。

当然，我们希望通过精心选择每个并行测试中要测试的修订版数量来最小化总成本，以确定 $R\_{ENBUG}$。如果采取最优策略，最小期望总成本是多少？

输入

输入包含一个单独的测试用例，具有以下格式。

$R\_{PASS}$ $R\_{RC}$ $K$
$T\_0$ $T\_1$ ... $T\_K$

$R\_{PASS}$ 和 $R\_{RC}$ 是表示测试通过和失败的我们软件的修订版号的整数。满足 $1 \\le R\_{PASS} \\lt R\_{RC} \\le 1{,}000$。$K$（$1 \\le K \\le 30$）是我们可以在单个并行测试中测试的最大修订版数量。$T\_i$ 是表示并行测试中有 $i$ 个测试失败时的成本的整数（$0 \\le i \\le K$）。可以假设 $1 \\le T\_0 \\le T\_1 \\le \\cdots \\le T\_K \\le 100{,}000$。

输出

输出最小期望总成本。输出的误差不应大于 $0.0001$。

示例输入 1

1 10 2
1 1 1```

### 示例输出 1

```plain
2.0```

* * *

### 示例输入 2

```plain
1 100 1
100 100```

### 示例输出 2

```plain
670.7070707```

* * *

### 示例输入 3

```plain
100 200 4
1 1 2 2 3```

### 示例输出 3

```plain
4.6400000```

* * *

### 示例输入 4

```plain
2 3 4
1 2 3 4 5```

### 示例输出 4

```plain
0.0```

* * *

### 示例输入 5

```plain
998 1000 4
10 100 1000 10000 100000```

### 示例输出 5

```plain
55.0```