配点: 100 点
JOI国家是 N 状态组成,每个状态都有 它们的编号最大为 1 减去 N 。2022 JOI国家将举行总统选举。在这次选举中,每个州都进行投票,获胜的候选人将被分配到该州。 1 获得选票。
现在,正在竞选总统的理惠认为,她会利用她的演讲来增强对自己的信心并赢得选举。具体来说,演讲的结果如下: 总演讲时间在
- 州 i (1 \leqq i \leqq N中) A_i 当到达时间时, 1 可以获得投票。
- 州 i (1 \leqq i \leqq N中) B_i 当时间到达时,协作者 1 你可以找到人。获得的协作者可以进行演讲,增加总的演讲时间。
- 然而,国家 在某些情况下,可能无法获得 i 的合作,在这种情况下 该信息以 B_i = -1 形式给出。否则,B_i \geqq A_i 有保证。
请注意,该状态 i (1 \leqq i \leqq N) 是状态 发表 i 以外的演讲,1 同时处于两种状态 2 也可以由多人发言。例如,同时处于一种状态 2 人 x 如果您进行时间演讲,则该状态的总演讲时间为 2x 时间增加。然而,讲话时间不必是整数。另外,假设可以忽略在状态之间行驶所需的时间。
随着投票日的临近,Rie 正在努力实现她的目标。 K 我想尽快获得选票。
给定状态数量以及每个状态的信息,K 编写一个程序来查找收集选票所需的最短时间。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
在标准输出上, 计算所有带有K 收集选票所需的最短时间。 输出为 1 行。与正确答案的绝对误差是 0.01 如果您输出如下答案,它将被视为正确答案。输出必须采用以下格式之一:
- 整数.(例:
123,0,-2022) - 整数,半角周期,
一种格式,由一系列最多为0 减去 9 的数字组成,且不使用空格分隔。输出小数点后的位数没有限制。 (例如:
123.4,-123.00,0.00288)
例如,
不要以指数表示法输出,如1.23456e+05 呀
请注意,它可能是 1.23456e5 。
制約
- 1 \leqq N \leqq 500.
- 1 \leqq K \leqq N.
- 1 \leqq A_i \leqq 1\,000 (1 \leqq i \leqq N).
- A_i \leqq B_i \leqq 1\,000 或 至少 B_i = -1 (1 \leqq i \leqq N).
小課題
- (5 点) B_i = -1 (1 \leqq i \leqq N).
- (5 点) B_i = -1 或 至少 B_i = A_i (1 \leqq i \leqq N).
- (11 点) N \leqq 7.
- (12 点) N \leqq 20.
- (33 点) N \leqq 100.
- (11 点) K = N.
- (23 点)没有额外的限制。
入力例 1
3 3 1 5 2 3 4 5
出力例 1
5.500000000000000
如果您按照以下顺序进行竞选活动,5.5 您可以及时获得每个州的选票。
- 理惠桑是状态 2 在 2 发表一次演讲并获得该州的选票。 更多内容请参见
- 理惠桑是状态 2 以及进一步 1 发表一次演讲并获得国家的合作。
- Rie 和合作者 1 人民就是国家 3 在 2 发表一次演讲并获得该州的选票。 更多内容请参见
- Rie 和合作者 1 人民就是国家 1 在 0.5 发表一次演讲并获得该州的选票。 更多内容请参见
此输入示例是一个小作业。 3, 4, 5, 6, 7 满足约束。
入力例 2
7 4 4 -1 11 -1 6 -1 12 -1 36 -1 11 -1 20 -1
出力例 2
32.000000000000000
如果您按照以下顺序进行竞选活动,32 及时 4 可以获得投票。
- 理惠桑是状态 1 在 4 发表一次演讲并获得该州的选票。 更多内容请参见
- 理惠桑是状态 2 在 11 发表一次演讲并获得该州的选票。 更多内容请参见
- 理惠桑是状态 3 在 6 发表一次演讲并获得该州的选票。 更多内容请参见
- 理惠桑是状态 6 在 11 发表一次演讲并获得该州的选票。 更多内容请参见
此输入示例是一个小作业。 1, 2, 3, 4, 5, 7 满足约束。
入力例 3
5 3 4 -1 5 -1 6 -1 7 7 8 8
出力例 3
11.500000000000000
如果您按照以下顺序进行竞选活动,11.5 及时 3 可以获得投票。
- 理惠桑是状态 4 在 7 发表一次演讲以赢得该州的选票和盟友。
- 理惠桑是状态 1 在 4 发表一次演讲并获得该州的选票。与此同时,合作者 1 人民就是国家 2 在 4 发表一次演讲。
- Rie 和合作者 1 人民就是国家 2 在 0.5 发表一次演讲并获得该州的选票。 更多内容请参见
此输入示例是一个小作业。 2, 3, 4, 5, 7 满足约束。
入力例 4
7 5 28 36 11 57 20 35 19 27 31 33 25 56 38 51
出力例 4
62.166666666666664
此输入示例是一个小作业。 3, 4, 5, 7 满足约束。
入力例 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
出力例 5
644.203571428571422
此输入示例是一个小作业。 4, 5, 7 满足约束。