{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003e\u003c/h2\u003e\n\n\u003cp\u003e\nWe are developing the world\u0027s 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} \u0026lt; R_{ENBUG} \\leq R_{RC}$) in which our software started to fail, we must test our product revision-by-revision.\n\u003c/p\u003e\n\n\u003cp\u003e\nHere, we can assume the following conditions:\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e When we test at the revision $R$, the test passes if $R \u0026lt; R_{ENBUG}$, or fails otherwise.\u003c/li\u003e\n\u003cli\u003e It is equally possible, which revision between $R_{PASS} + 1$ and $R_{RC}$ is $R_{ENBUG}$.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nFrom the first assumption, we don\u0027t 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\u0027t use all the $K$ devices.\n\u003c/p\u003e\n\n\u003cp\u003e\nParallel 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 \\leq i \\leq K$). And if we run parallel testings multiple times, the total cost is the sum of their costs.\n\u003c/p\u003e\n\n\u003cp\u003e\nOf 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?\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\nThe input consists of a single test case with the following format.\u003cbr\u003e\n\u003cbr\u003e\n$R_{PASS}$ $R_{RC}$ $K$\u003cbr\u003e\n$T_0$ $T_1$ ... $T_K$\n\u003c/p\u003e\n\n\u003cp\u003e\n$R_{PASS}$ and $R_{RC}$ are integers that represent the revision numbers of our software at which the test passed and failed, respectively. $1 \\leq R_{PASS} \u0026lt; R_{RC} \\leq 1,000$ holds. $K$ ($1 \\leq K \\leq 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 \\leq i \\leq K$). You can assume $1 \\leq T_0 \\leq T_1 \\leq ... \\leq T_K \\leq 100,000$.\n\u003c/p\u003e\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\nOutput the minimum expected value of the total cost. The output should not contain an error greater than 0.0001.\n\u003c/p\u003e\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 10 2\n1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 100 1\n100 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e670.7070707\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e100 200 4\n1 1 2 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4.6400000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3 4\n1 2 3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e998 1000 4\n10 100 1000 10000 100000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e55.0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}