Minimizing Speech Time for Electoral Victory

In the JOI Republic there are N states numbered from \(1\) to \(N\). In the year 2022, a presidential election will be held – each state holds its own vote, and the winner of the state gains one ballot.

Rie is running for president, and she plans to win by giving speeches to raise her reliability. When she gives a speech in a state, the following events may occur:

• If the total speech time in state \(i\) reaches \(A_i\) hours, then Rie wins that state’s vote.
• If the total speech time in state \(i\) reaches \(B_i\) hours, then she gains an assistant from state \(i\). (Note that if state \(i\) cannot provide an assistant, then \(B_i = -1\); otherwise, it is guaranteed that \(B_i > A_i\).)

An assistant from state \(i\) can give speeches in any state other than \(i\). Multiple people can speak simultaneously in the same state – for example, if two people both speak for \(x\) hours at the same time in a state, the total speech time in that state increases by \(2x\) hours. (The speech time need not be an integer, and you may ignore travel time between states.)

With election day fast approaching, Rie wishes to obtain K votes as quickly as possible. Determine the minimum number of hours required so that, by optimally scheduling speeches (by herself and her assistants), Rie can garner K votes.

The effect of speech time is cumulative – by assigning several speakers (each having at most \(T\) hours available) to a state, the total speech time in that state can be increased to any desired amount up to \((\#\text{speakers}) \times T\) hours.

Note about strategy: In any state with \(B_i \neq -1\), Rie can choose either to invest \(A_i\) hours (using one speaker) to win that state’s vote, or, if possible, invest \(B_i\) hours to win the vote and also recruit an assistant – which in turn gives an extra \(T\) hours of available speech time. The trade‐off is that while the assistant option costs more time (\(B_i\) instead of \(A_i\)), it increases the available human resource for speech.

Your task is to compute the minimum time \(T\) (in hours) such that, if the speeches are scheduled optimally, Rie can obtain at least \(K\) votes.

It is guaranteed that \(1 \le N \le 10^5\) and \(1 \le K \le N\). For each state \(i\), \(1 \le A_i \le 10^9\) and either \(B_i = -1\) or \(A_i < B_i \le 10^9\).

Input format: The first line contains two integers \(N\) and \(K\). Each of the following \(N\) lines contains two integers: \(A_i\) and \(B_i\). (Here, \(B_i = -1\) means that state \(i\) does not offer an assistant.)

Output format: Output the minimum number of hours needed. An absolute or relative error of at most \(10^{-6}\) is acceptable.

inputFormat

The first line contains two integers \(N\) and \(K\) separated by a space.

Then \(N\) lines follow. The \(i\)th of these lines contains two integers \(A_i\) and \(B_i\), where if \(B_i = -1\), it means state \(i\) cannot provide an assistant.

All numbers are separated by spaces.

outputFormat

Output a single floating-point number \(T\): the minimum number of hours needed to obtain at least \(K\) votes. An absolute or relative error of at most \(10^{-6}\) is permitted.

sample

3 2
1 2
2 -1
2 3

2.000000