Problem Description

The JOI Republic has $N$ states, numbered $1 \sim N$. In 2022, the JOI Republic will hold a presidential election. The election will be held separately in each state. The winner in each state will obtain one electoral vote from that state.

Rie will run for president, and she is planning to win the election. She decides to increase her credibility by giving speeches. After she gives speeches, the following events may occur.

• If the total speech time in the $i$-th state reaches $A_i$ hours, she will win one electoral vote from that state.
• If the total speech time in the $i$-th state reaches $B_i$ hours, she will gain one 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 \geq A_i$.

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

Election day is approaching, and Rie wants to obtain $K$ electoral votes as quickly as possible.

Given the number of states and the information for each state, write a program to compute the minimum time required (in hours) to obtain $K$ electoral votes.

Input Format

The first line contains a positive integer $N$.

The second line contains a positive integer $K$.

The next $N$ lines describe the states. The $i$-th of these lines contains two positive integers $A_i, B_i$.

Output Format

Print one line containing one number: the minimum time required (in hours) to obtain $K$ electoral votes.

If the absolute difference between your output and the correct answer is at most $0.01$, then your submission will be judged correct. Your output must be in one of the following formats:

• An integer (examples: 123, 0, -2022).
• A sequence consisting of an integer, a dot, and a string of digits $0 \sim 9$. It must not contain any separators. The number of digits after the decimal point is unlimited (examples: 123.4, -123.00, 0.00288).

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

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

Hint

[Sample Explanation #1]

By giving speeches according to the following plan, Rie will win the electoral vote in every state within $5.5$ hours.

• Give a speech in the $2$-nd state for $2$ hours and win one electoral vote.
• Give another speech in the $2$-nd state for $1$ hour and gain one collaborator.
• Give a speech in the $3$-rd state together with the collaborator for $2$ hours and win one electoral vote.
• Give a speech in the $1$-st state together with the collaborator for $0.5$ hours and win one electoral vote.

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

[Sample Explanation #2]

By giving speeches according to the following plan, Rie will obtain $4$ electoral votes within $32$ hours.

• Give a speech in the $1$-st state for $4$ hours and win one electoral vote.
• Give a speech in the $2$-nd state for $11$ hours and win one electoral vote.
• Give a speech in the $3$-rd state for $6$ hours and win one electoral vote.
• Give a speech in the $6$-th state for $11$ hours and win one electoral vote.

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

[Sample Explanation #3]

By giving speeches according to the following plan, Rie will obtain $3$ electoral votes within $11.5$ hours.

• Give a speech in the $4$-th state for $7$ hours, win one electoral vote, and gain one collaborator.
• Give a speech in the $1$-st state for $4$ hours and win one electoral vote. At the same time, the collaborator gives a speech in the $2$-nd state for $4$ hours.
• Give a speech in the $2$-nd state together with the collaborator for $0.5$ hours and win one electoral vote.

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

[Sample Explanation #4]

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

[Sample Explanation #5]

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

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le K \le N \le 500$, $1 \le A_i \le 1000$, and $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”.

Translated by ChatGPT 5