JOI 共和国由 $N$ 个州组成，编号为 $1$ 到 $N$。2022 年，JOI 共和国将举行总统选举。选举将在每个州进行，在某个州获胜的候选人将获得该州的选票。

Rie 将参加总统竞选。她计划通过发表演讲来提高自己的可靠度。在她发表演讲后，会发生以下情况：

• 如果州 $i$ ($1 \le i \le N$) 的演讲总时长达到 $A_i$ 小时，她将获得州 $i$ 的选票。
• 如果州 $i$ ($1 \le i \le N$) 的演讲总时长达到 $B_i$ 小时，她将从州 $i$ 获得一名合作者。此后，该合作者将能够发表演讲以增加演讲总时长。
• Rie 可能无法从州 $i$ 获得任何合作者。在这种情况下，$B_i = -1$。否则，保证 $B_i \ge A_i$ 成立。

来自州 $i$ ($1 \le i \le N$) 的合作者可以在州 $i$ 之外发表演讲。多个人可以同时在同一个州发表演讲。例如，如果两个人同时在某个州发表演讲 $x$ 小时，该州的演讲总时长将增加 $2x$ 小时。演讲时长不需要是整数。我们忽略州与州之间的旅行时间。

由于选举日即将来临，Rie 希望尽快获得 $K$ 张选票。

给定州数以及每个州的信息，编写一个程序，计算获得 $K$ 张选票所需的最少小时数。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

向标准输出写入一行。输出应包含获得 $K$ 张选票所需的最少小时数。如果你的答案与正确答案的绝对误差不超过 $0.01$，则你的解将被判定为正确。输出应采用以下格式之一：

• 一个整数。（例如：123, 0, -2022）
• 由一个整数、一个小数点和一串 $0$ 到 $9$ 之间的数字组成的序列。不应包含分隔符。小数点后的位数没有限制。（例如：123.4, -123.00, 0.00288）

输出不应使用科学计数法。例如，1.23456e+05 和 1.23456e5 是不允许的。

数据范围

• $1 \le N \le 500$
• $1 \le K \le N$
• $1 \le A_i \le 1\,000$ ($1 \le i \le N$)
• $A_i \le B_i \le 1\,000$ 或 $B_i = -1$ ($1 \le i \le N$)

子任务

1. (5 分) $B_i = -1$ ($1 \le i \le N$)
2. (5 分) $B_i = -1$ 或 $B_i = A_i$ ($1 \le i \le N$)
3. (11 分) $N \le 7$
4. (12 分) $N \le 20$
5. (33 分) $N \le 100$
6. (11 分) $K = N$
7. (23 分) 无附加限制

样例

样例输入 1

3
3
1 5
2 3
4 5

样例输出 1

5.500000000000000

说明 1

如果竞选活动按以下顺序进行，Rie 将在 5.5 小时内获得每个州的选票：

1. Rie 在州 2 发表演讲 2 小时，获得州 2 的选票。
2. 此外，Rie 在州 2 发表演讲 1 小时，从州 2 获得一名合作者。
3. Rie 和该合作者在州 3 发表演讲 2 小时，Rie 获得州 3 的选票。
4. Rie 和该合作者在州 1 发表演讲 0.5 小时，Rie 获得州 1 的选票。

样例输入 2

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

样例输出 2

32.000000000000000

说明 2

如果竞选活动按以下顺序进行，Rie 将在 32 小时内获得 4 张选票：

1. Rie 在州 1 发表演讲 4 小时，获得州 1 的选票。
2. Rie 在州 2 发表演讲 11 小时，获得州 2 的选票。
3. Rie 在州 3 发表演讲 6 小时，获得州 3 的选票。
4. Rie 在州 6 发表演讲 11 小时，获得州 6 的选票。

样例输入 3

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

样例输出 3

11.500000000000000

说明 3

如果竞选活动按以下顺序进行，Rie 将在 11.5 小时内获得 3 张选票：

1. Rie 在州 4 发表演讲 7 小时，获得州 4 的选票并从州 4 获得一名合作者。
2. Rie 在州 1 发表演讲 4 小时，获得州 1 的选票。同时，该合作者在州 2 发表演讲 4 小时。
3. Rie 和该合作者在州 2 发表演讲 0.5 小时，Rie 获得州 2 的选票。

样例输入 4

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

样例输出 4

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

样例输出 5

644.203571428571422