第 3 题 赢得选举 (letswintheelection)

时间限制 1.0 s · 空间限制 256 MB · 105 个测试点 · 特殊 Judge

本题使用文件输入输出：输入文件 letswintheelection.in，输出文件 letswintheelection.out。

题目描述

JOI 共和国有 $N$ 个州，编号为 $1 \sim N$。在 2022 年，JOI 共和国将举行总统大选。选举将在每个州分别举行。每个州的获胜者将赢得该州的一张选票。

Rie 将竞选总统，她正计划赢得选举。她决定以发表演讲的方式来提高自己的可靠程度。在她发表演讲后，下列事件可能会发生。

• 如果在第 $i$ 个州的总演讲时间达到了 $A_i$ 小时，她将赢得该州的一张选票。
• 如果在第 $i$ 个州的总演讲时间达到了 $B_i$ 小时，她将获得一名来自该州的协作者。
• 有可能 Rie 在第 $i$ 个州无法获得协作者。此种情况下，$B_i = -1$，否则保证 $B_i \ge A_i$。

来自第 $i$ 个州的协作者可以在第 $i$ 个州外发表演讲。多个人可以同时在同一个州发表演讲。举个例子，如果两个人在某个州同时发表了 $x$ 小时的演讲，则该州的总演讲时间将增加 $2x$ 小时。演讲的时间不必是整数个小时。我们可以忽略在两州之间的交通耗时。

大选日快到了，Rie 想要尽快得到 $K$ 张选票。

给定州的数量和每个州的信息，写一个程序计算得到 $K$ 张选票的最小耗时（以小时为单位）。

输入格式

第一行，一个正整数 $N$。

第二行，一个正整数 $K$。

接下来 $N$ 行，第 $i$ 行两个正整数 $A_i, B_i$。

输出格式

输出一行，一个数，表示得到 $K$ 张选票的最小耗时（以小时为单位）。

如果你的输出与正确答案的差值的绝对值不超过 $0.01$ 则你的提交将被判断为正确。你的输出应使用如下格式：

• 一个整数（例：123，0，-2022）。
• 一个依次包含一个整数，一个句点，和一个仅包含 0 ~ 9 的数位的字符串的序列。其不应当包含分隔符。对小数点后的数位长度无限制（例：123.4，-123.00，0.00288）。

输出不应使用指数表示法。举个例子，1.23456e+05 和 1.23456e5 不被允许。

样例

样例 1

输入：

3
3
1 5
2 3
4 5

输出：

5.500000000000000

样例 2

输入：

7
4
4 -1
11 -1
6 -1
12 -1
36 -1
11 -1
20 -1

输出：

32.000000000000000

样例 3

输入：

5
3
4 -1
5 -1
6 -1
7 7
8 8

输出：

11.500000000000000

样例 4

输入：

7
5
28 36
11 57
20 35
19 27
31 33
25 56
38 51

输出：

62.166666666666664

样例 5

输入：

20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260

输出：

644.203571428571422

提示

【样例解释 #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 T3 「選挙で勝とう / Let’s Win the Election」