Problem Description

The country of JOI consists of $ N $ states, each labeled from $ 1 $ to $ N $. In 2022, a presidential election will be held in JOI. In this election, voting will take place in each state, and the candidate who wins will receive the 1 vote allocated to that state.

Rie, who is running for president, plans to increase her credibility through speeches to win the election. Specifically, the following will happen through speeches:

• When the total speech time in state $ i $ ($1 \leq i \leq N$) reaches $ A_i $ hours, she can acquire the 1 vote allocated to that state.
• When the total speech time in state $ i $ ($1 \leq i \leq N$) reaches $ B_i $ hours, she can acquire 1 supporter. The acquired supporter can then give speeches to increase the total speech time.
• However, it is possible that no supporter can be acquired from state $ i $, in which case the information is given as $ B_i = -1 $. Otherwise, it is guaranteed that $B_i \geq A_i$.

Note that supporters acquired from state $ i $ ($1 \leq i \leq N$) can give speeches in states other than $ i $, and more than one person can give speeches simultaneously in a single state. For example, if two people give speeches for $ x $ hours simultaneously in a state, the total speech time in that state increases by $ 2x $ hours. The speech time does not need to be an integer, and the time to move between states is negligible.

With the election day approaching, Rie wants to acquire her target of $ K $ votes as quickly as possible.

Given the number of states and information about each state, create a program to find the minimum time required to collect $ K $ votes.

Input Format

The input is given from the standard input in the following format. All values are integers.

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

Output Format

Output to the standard output the minimum time required to collect $ K $ votes in one line. The answer will be considered correct if the absolute error is within $ 0.01 $. The output must be in one of the following formats:

• An integer. (e.g., 123, 0, -2022)
• An integer followed by a period and a sequence of digits from 0 to 9 without any spaces. There is no limit on the number of digits after the decimal point. (e.g., 123.4, -123.00, 0.00288)

For example, do not output in exponential notation such as 1.23456e+05 or 1.23456e5.

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/Hints

Constraints

• $1 \leq N \leq 500$.
• $1 \leq K \leq N$.
• $1 \leq A_i \leq 1,000$ ($1 \leq i \leq N$).
• $A_i \leq B_i \leq 1,000$ or $ B_i = -1 $ ($1 \leq i \leq N$).

Subtasks

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

Sample Explanation 1

By conducting election activities in the following order, all states' votes can be acquired in $ 5.5 $ hours:
1. Rie gives a speech for $ 2 $ hours in state $ 2 $ and acquires that state's vote.
2. Rie gives another speech for $ 1 $ hour in state $ 2 $ and acquires a supporter from that state.
3. Rie and the supporter give speeches for $ 2 $ hours in state $ 3 $ and acquire that state's vote.
4. Rie and the supporter give speeches for $ 0.5 $ hours in state $ 1 $ and acquire that state's vote. This input example satisfies the constraints of subtasks $ 3, 4, 5, 6, 7 $.

Sample Explanation 2

By conducting election activities in the following order, $ 4 $ votes can be acquired in $ 32 $ hours:
1. Rie gives a speech for $ 4 $ hours in state $ 1 $ and acquires that state's vote.
2. Rie gives a speech for $ 11 $ hours in state $ 2 $ and acquires that state's vote.
3. Rie gives a speech for $ 6 $ hours in state $ 3 $ and acquires that state's vote.
4. Rie gives a speech for $ 11 $ hours in state $ 6 $ and acquires that state's vote. This input example satisfies the constraints of subtasks $ 1, 2, 3, 4, 5, 7 $.

Sample Explanation 3

By conducting election activities in the following order, $ 3 $ votes can be acquired in $ 11.5 $ hours:
1. Rie gives a speech for $ 7 $ hours in state $ 4 $ and acquires that state's vote and supporter.
2. Rie gives a speech for $ 4 $ hours in state $ 1 $ and acquires that state's vote. Simultaneously, the supporter gives a speech for $ 4 $ hours in state $ 2 $.
3. Rie and the supporter give speeches for $ 0.5 $ hours in state $ 2 $ and acquire that state's vote. This input example satisfies the constraints of subtasks $ 2, 3, 4, 5, 7 $.

Sample Explanation 4

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

Sample Explanation 5

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

见题面 Input 部分

见题面 Output 部分