题目描述

译自 JOI 2022 Final T3「選挙で勝とう / Let's Win the Election」

JOI 共和国由 $N$ 个州组成，现在 JOI 共和国正在进行选举。

理恵想要赢得选举，她决定以发表演讲的方式来提高自己的支持率，具体的，她可以发表任意时间长度的演讲，这些演讲会造成一定的影响：

• 如果在这个州的演讲时间达到 $A_i$，那么她将会赢得一张选票；
• 如果在这个州的演讲时间达到 $B_i$，那么她将会赢得一名协作者，协作者可以与她同时在任何州发表演讲，如果多人同时在一个州发表演讲，计入多倍演讲时间。
• 有可能无法获得协作者，此时 $B_i=-1$，此外我们保证 $B_i\ge A_i$。

理恵想尽快得到 $K$ 张选票，请计算最小的演讲时间。

输入格式

第一行一个整数 $N$。

第二行一个整数 $K$。

接下来 $N$ 行，一行两个整数 $A_i,B_i$。

输出格式

输出一个实数，表示需要的最小演讲时间，你的答案与标准答案的绝对误差不应超过 $0.01$。

3
3
1 5
2 3
4 5

5.500000000000000

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

32.000000000000000

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

11.500000000000000

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

62.166666666666664

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\le N\le 500$，$1\le K\le N$，$1\le A_i\le 10^3$，$A_i\le B_i\le 10^3$ 或者 $B_i=-1$。