Problem Description

In the JOI Republic, there are $N$ states numbered from $1$ to $N$. In 2022, the JOI Republic will hold a presidential election. The election will take place in each state separately. The winner in each state will earn one vote from that state.

Rie is running for president and is planning to win the election. She decides to give speeches to increase her credibility. After she gives a speech, the following events may occur:

• If the total speech time in the $i$-th state reaches $A_i$ hours, she will earn one vote from that state.
• If the total speech time in the $i$-th state reaches $B_i$ hours, she will gain a collaborator from that state.
• It is possible that Rie cannot gain a collaborator in the $i$-th state. In this case, $B_i = -1$; otherwise, it is guaranteed that $B_i > A_i$.

A collaborator from the $i$-th state can give speeches outside the $i$-th state. Multiple people can give speeches simultaneously in the same state. For example, if two people give speeches for $x$ hours in a state simultaneously, the total speech time in that state will increase by $2x$ hours. The speech time does not need to be an integer number of hours. We can ignore the travel time between states.

The election day is approaching, and Rie wants to get $K$ votes as quickly as possible.

Given the number of states and information about each state, write a program to calculate the minimum time (in hours) required to get $K$ votes.

Input Format

The first line contains a positive integer $N$.

The second line contains a positive integer $K$.

The next $N$ lines, the $i$-th line contains two positive integers $A_i$ and $B_i$.

Output Format

Output one line containing a number representing the minimum time (in hours) required to get $K$ votes.

Your output will be considered correct if the absolute difference between your output and the correct answer is no more than $0.01$. Your output should be formatted as follows:

• An integer (e.g., 123, 0, -2022).
• A sequence consisting of an integer, a period, and a string of digits from $0$ to $9$ without separators. There is no restriction on the length of digits after the decimal point (e.g., 123.4, -123.00, 0.00288).

Do not use exponential notation. For example, 1.23456e+05 and 1.23456e5 are not allowed.

Sample Input and Output

Sample Input #1

3
3
1 5
2 3
4 5

Sample Output #1

5.500000000000000

Sample Input #2

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

Sample Output #2

32.000000000000000

Sample Input #3

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

Sample Output #3

11.500000000000000

Sample Input #4

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

Sample Output #4

62.166666666666664

Sample Input #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

Sample Output #5

644.203571428571422

Notes

[Sample Explanation #1]

By following this plan, Rie will win votes from each state in $5.5$ hours:

• Give a speech in the $2$nd state for $2$ hours, winning one vote.
• Give another speech in the $2$nd state for $1$ hour, gaining a collaborator.
• Give a speech in the $3$rd state with the collaborator for $2$ hours, winning one vote.
• Give a speech in the $1$st state with the collaborator for $0.5$ hours, winning one vote.

This example satisfies the properties of subtasks $3, 4, 5, 6, 7$.

[Sample Explanation #2]

By following this plan, Rie will win $4$ votes in $32$ hours:

• Give a speech in the $1$st state for $4$ hours, winning one vote.
• Give a speech in the $2$nd state for $11$ hours, winning one vote.
• Give a speech in the $3$rd state for $6$ hours, winning one vote.
• Give a speech in the $6$th state for $11$ hours, winning one vote.

This example satisfies the constraints of subtasks $1, 2, 3, 4, 5, 7$.

[Sample Explanation #3]

By following this plan, Rie will win $3$ votes in $11.5$ hours:

• Give a speech in the $4$th state for $7$ hours, winning one vote and gaining a collaborator.
• Give a speech in the $1$st state for $4$ hours, winning one vote. Meanwhile, the collaborator gives a speech in the $2$nd state for $4$ hours.
• Give a speech in the $2$nd state with the collaborator for $0.5$ hours, winning one vote.

This example satisfies the constraints of subtasks $2, 3, 4, 5, 7$.

[Sample Explanation #4]

This example satisfies the constraints of subtasks $3, 4, 5, 7$.

[Sample Explanation #5]

This example satisfies the constraints of subtasks $4, 5, 7$.

[Data Range]

This problem is bundled test cases.

For $100\%$ of the data, $1 \le K \le N \le 500$, $1 \le A_i \le 1000$, $A_i \le B_i \le 1000$ or $B_i = -1$.

• Subtask $1$ ($5$ points): $B_i = -1$.
• Subtask $2$ ($5$ points): $B_i = -1$ or $B_i = A_i$.
• Subtask $3$ ($11$ points): $N \le 7$.
• Subtask $4$ ($12$ points): $N \le 20$.
• Subtask $5$ ($33$ points): $N \le 100$.
• Subtask $6$ ($11$ points): $K = N$.
• Subtask $7$ ($23$ points): No additional constraints.

Translated from JOI 2022 Final T3 "選挙で勝とう / Let's Win the Election"

见题面 Input 部分

见题面 Output 部分