P8162 [JOI 2022 Final] 让我们赢得选举 / Let's Win the Election

JOI 共和国有 $N$ 个州，编号为 $1 \sim N$。在 2022 年，JOI 共和国将举行总统大选。选举将在每个州分别举行。每个州的获胜者将赢得该州的一张选票。 Rie 将竞选总统，她正计划赢得选举。她决定以发表演讲的方式来提高自己的可靠程度。在她发表演讲后，下列事件可能会发生。 - 如果在第 $i$ 个州的总演讲时间达到了 $A_i$ 小时，她将赢得该州的一张选票。 - 如果在第 $i$ 个州的总演讲时间达到了 $B_i$ 小时，她将获得一名来自该州的协作者。 - 有可能 Rie 在第 $i$ 个州无法获得协作者。此种情况下，$B_i = -1$，否则保证 $B_i > A_i$。 来自第 $i$ 个州的协作者可以在第 $i$ 个州外发表演讲。多个人可以同时在同一个州发表演讲。举个例子，如果两个人在某个州同时发表了 $x$ 小时的演讲，则该州的总演讲时间将增加 $2 x$ 小时。演讲的时间不必是整数个小时。我们可以忽略在两州之间的交通耗时。 大选日快到了，Rie 想要尽快得到 $K$ 张选票。 给定州的数量和每个州的信息，写一个程序计算得到 $K$ 张选票的最小耗时（以小时为单位）。

无

无

**【样例解释 \#1】** 按照如下方案进行演讲，Rie 将在 $5.5$ 小时内赢得每个州的选票。 - 在第 $2$ 个州演讲 $2$ 个小时，赢得一张选票。 - 在第 $2$ 个州再演讲 $1$ 个小时，获得一个协作者。 - 在第 $3$ 个州与协作者一起演讲 $2$ 个小时，赢得一张选票。 - 在第 $1$ 个州与协作者一起演讲 $0.5$ 个小时，赢得一张选票。 这个样例满足子任务 $3, 4, 5, 6, 7$ 的性质。 **【样例解释 \#2】** 按照如下方案进行演讲，Rie 将在 $32$ 小时内赢得 $4$ 张选票。 - 在第 $1$ 个州演讲 $4$ 个小时，赢得一张选票。 - 在第 $2$ 个州演讲 $11$ 个小时，赢得一张选票。 - 在第 $3$ 个州演讲 $6$ 个小时，赢得一张选票。 - 在第 $6$ 个州演讲 $11$ 个小时，赢得一张选票。 这个样例满足子任务 $1, 2, 3, 4, 5, 7$ 的限制。 **【样例解释 \#3】** 按照如下方案进行演讲，Rie 将在 $11.5$ 小时内赢得 $3$ 张选票。 - 在第 $4$ 个州演讲 $7$ 个小时，赢得一张选票，并获得一个协作者。 - 在第 $1$ 个州演讲 $4$ 个小时，赢得一张选票。与此同时，协作者在第 $2$ 个州演讲 $4$ 个小时。 - 在第 $2$ 个州与协作者一起演讲 $0.5$ 个小时，赢得一张选票。 这个样例满足子任务 $2, 3, 4, 5, 7$ 的限制。 **【样例解释 \#4】** 这个样例满足子任务 $3, 4, 5, 7$ 的限制。 **【样例解释 \#5】** 这个样例满足子任务 $4, 5, 7$ 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** 对于 $100 \%$ 的数据，$1 \le K \le N \le 500$，$1 \le A_i \le 1000$，$A_i \le B_i \le 1000$ 或 $B_i = -1$。 - 子任务 $1$（$5$ 分）：$B_i = -1$。 - 子任务 $2$（$5$ 分）：$B_i = -1$ 或 $B_i = A_i$。 - 子任务 $3$（$11$ 分）：$N \le 7$。 - 子任务 $4$（$12$ 分）：$N \le 20$。 - 子任务 $5$（$33$ 分）：$N \le 100$。 - 子任务 $6$（$11$ 分）：$K = N$。 - 子任务 $7$（$23$ 分）：无特殊限制。 ---- **译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T3「[選挙で勝とう](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t3.pdf) / [Let's Win the Election](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t3-en.pdf)」**