Multisect

We are developing the world's coolest AI robot product. After a long struggle, we finally sent revision $R_{\mathrm{RC}}$ of the product to the QA team as a release candidate. They reported that some tests failed. Because we were too lazy to set up a continuous integration system, we have no idea when the software broke. We only know that every test passed at the past revision $R_{\mathrm{PASS}}$. To find the revision $R_{\mathrm{BUG}}$ ($R_{\mathrm{PASS}} < R_{\mathrm{BUG}} \le R_{\mathrm{RC}}$) at which the software started to fail, we have to test revisions one by one.

Assume the following.

• A test at revision $R$ passes if $R < R_{\mathrm{BUG}}$ and fails otherwise.
• Every revision from $R_{\mathrm{PASS}} + 1$ to $R_{\mathrm{RC}}$ is equally likely to be $R_{\mathrm{BUG}}$.

By the first assumption we do not need to test every revision. It is enough to find the revision $R$ such that the test at $R - 1$ passes and the test at $R$ fails. We have $K$ testing devices, so we can test up to $K$ different revisions at the same time. We call this a parallel test. Because of the testing environment, we cannot start new tests until the current parallel test finishes, even when it does not use all $K$ devices.

A parallel test has a cost. The more tests fail, the more it costs. If $i$ tests fail in a parallel test, its cost is $T_i$ ($0 \le i \le K$). When we run several parallel tests, the total cost is the sum of their costs.

We want to minimize the total cost of determining $R_{\mathrm{BUG}}$ by carefully choosing how many revisions, and which ones, to test in each parallel test. What is the minimum expected total cost under an optimal strategy?

The input is a single test case in the following format.

RPASS RRC K
T0 T1 ... TK

$R_{\mathrm{PASS}}$ and $R_{\mathrm{RC}}$ are integers, the revision numbers at which the test passed and failed, respectively, and $1 \le R_{\mathrm{PASS}} < R_{\mathrm{RC}} \le 1000$. $K$ ($1 \le K \le 30$) is the maximum number of revisions that one parallel test can cover. $T_i$ is an integer, the cost of a parallel test in which $i$ tests fail ($0 \le i \le K$), and $1 \le T_0 \le T_1 \le \cdots \le T_K \le 100000$.

Print the minimum expected total cost as an irreducible fraction in the form p/q on one line, where $p$ and $q$ are coprime integers and $q \ge 1$. When the value is an integer, print it with denominator 1 (for example, print 0/1 for 0).