멀티섹트

우리는 세계에서 가장 멋진 AI 로봇 제품을 개발하고 있다. 오랜 고생 끝에 리비전 $R_{\mathrm{RC}}$의 제품을 출시 후보로 QA 팀에 보냈는데, 몇몇 테스트가 실패했다는 보고가 돌아왔다. 지속적 통합 시스템을 갖추지 않은 탓에 소프트웨어가 언제부터 망가졌는지 알 수 없다. 아는 것은 과거의 리비전 $R_{\mathrm{PASS}}$에서는 모든 테스트가 통과했다는 사실뿐이다. 테스트가 실패하기 시작한 리비전 $R_{\mathrm{BUG}}$ ($R_{\mathrm{PASS}} < R_{\mathrm{BUG}} \le R_{\mathrm{RC}}$)를 알아내려면 리비전을 하나씩 테스트해야 한다.

다음을 가정한다.

• 리비전 $R$을 테스트하면 $R < R_{\mathrm{BUG}}$일 때 통과하고, 그렇지 않으면 실패한다.
• $R_{\mathrm{PASS}} + 1$ 이상 $R_{\mathrm{RC}}$ 이하의 각 리비전이 $R_{\mathrm{BUG}}$일 확률은 모두 같다.

첫 번째 가정 덕분에 모든 리비전을 테스트할 필요는 없다. 리비전 $R - 1$의 테스트는 통과하고 리비전 $R$의 테스트는 실패하는 $R$을 찾으면 된다. 테스트 장비는 $K$대 있다. 이 장비로 서로 다른 리비전을 한 번에 최대 $K$개까지 동시에 테스트할 수 있다. 이를 병렬 테스트라 부른다. 테스트 환경의 제약 때문에, $K$대를 모두 쓰지 않았더라도 진행 중인 병렬 테스트가 끝나기 전에는 새 테스트를 시작할 수 없다.

병렬 테스트에는 비용이 든다. 실패한 테스트가 많을수록 비용이 커진다. 한 번의 병렬 테스트에서 $i$개의 테스트가 실패하면 그 비용은 $T_i$다 ($0 \le i \le K$). 병렬 테스트를 여러 번 하면 총비용은 각 비용의 합이다.

매번 몇 개의 리비전을, 어느 리비전을 테스트할지 잘 골라 $R_{\mathrm{BUG}}$를 알아내는 총비용을 최소로 만들고 싶다. 최적의 전략을 쓸 때 총비용의 기댓값의 최솟값은 얼마인가?

입력은 하나의 테스트 케이스로 이루어지며 형식은 다음과 같다.

RPASS RRC K
T0 T1 ... TK

$R_{\mathrm{PASS}}$와 $R_{\mathrm{RC}}$는 각각 테스트가 통과한 리비전과 실패한 리비전의 번호이며 정수다. $1 \le R_{\mathrm{PASS}} < R_{\mathrm{RC}} \le 1000$이다. $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 100000$이다.

총비용의 기댓값의 최솟값을 기약분수 p/q 형태로 한 줄에 출력한다. $p$와 $q$는 서로소인 정수이고 $q \ge 1$이다. 값이 정수이면 분모를 1로 하여 출력한다 (예를 들어 값이 0이면 0/1).