MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

We are developing the world's coolest AI robot product. After the long struggle, we finally managed to send our product at revision $R\_{RC}$ to QA team as a release candidate. However, they reported that some tests failed! Because we were too lazy to set up a continuous integration system, we have no idea when our software corrupted. We only know that the software passed all the test at the past revision $R\_{PASS}$. To determine the revision $R\_{ENBUG}$ ($R\_{PASS} \\lt R\_{ENBUG} \\le R\_{RC}$) in which our software started to fail, we must test our product revision-by-revision.

Here, we can assume the following conditions:

• When we test at the revision $R$, the test passes if $R \\lt R\_{ENBUG}$, or fails otherwise.
• It is equally possible, which revision between $R\_{PASS} + 1$ and $R\_{RC}$ is $R\_{ENBUG}$.

From the first assumption, we don't need to test all the revisions. All we have to do is to find the revision $R$ such that the test at $R - 1$ passes and the test at $R$ fails. We have $K$ testing devices. Using them, we can test at most $K$ different revisions simultaneously. We call this "parallel testing". By the restriction of the testing environment, we cannot start new tests until a current parallel testing finishes, even if we don't use all the $K$ devices.

Parallel testings take some cost. The more tests fail, the more costly the parallel testing becomes. If $i$ tests fail in a parallel testing, its cost is $T\_i$ ($0 \\le i \\le K$). And if we run parallel testings multiple times, the total cost is the sum of their costs.

Of course we want to minimize the total cost to determine $R\_{ENBUG}$, by choosing carefully how many and which revisions to test on each parallel testing. What is the minimum expected value of the total cost if we take an optimal strategy?

Input

The input consists of a single test case with the following format.

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

$R\_{PASS}$ and $R\_{RC}$ are integers that represent the revision numbers of our software at which the test passed and failed, respectively. $1 \\le R\_{PASS} \\lt R\_{RC} \\le 1{,}000$ holds. $K$ ($1 \\le K \\le 30$) is the maximum number of revisions we can test in a single parallel testing. $T\_i$ is an integer that represents the cost of a parallel testing in which $i$ tests fail ($0 \\le i \\le K$). You can assume $1 \\le T\_0 \\le T\_1 \\le \\cdots \\le T\_K \\le 100{,}000$.

Output

Output the minimum expected value of the total cost. The output should not contain an error greater than $0.0001$.

Sample Input 1

1 10 2
1 1 1```

### Output for the Sample Input 1

```plain
2.0```

* * *

### Sample Input 2

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

### Output for the Sample Input 2

```plain
670.7070707```

* * *

### Sample Input 3

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

### Output for the Sample Input 3

```plain
4.6400000```

* * *

### Sample Input 4

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

### Output for the Sample Input 4

```plain
0.0```

* * *

### Sample Input 5

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

### Output for the Sample Input 5

```plain
55.0```

* * *