문제

JOI 国は $N$ 個の州からなり，それぞれ $1$ から $N$ までの番号が付けられている．2022 年，JOI 国では大統領選挙が開催されることになった．この選挙では各州で投票が行われ，勝った候補者がその州に割り当てられている $1$ 票を獲得する．

さて，大統領選挙に出馬する理恵さんは，演説によって自身への信頼度を上げ，選挙で勝とうと考えた．演説により，具体的には次のことが起こる．

• 州 $i$ ($1 \le i \le N$) での合計演説時間が $A_i$ 時間に達すると，その州に割り当てられている $1$ 票を獲得できる．
• 州 $i$ ($1 \le i \le N$) での合計演説時間が $B_i$ 時間に達すると，協力者 $1$ 人を得ることができる．得られた協力者は，それ以降演説を行い，合計演説時間を増やすことができる．
• ただし，州 $i$ からの協力者を得られない場合もあり，その場合は $B_i = -1$ として情報が与えられる．それ以外の場合は，$B_i \ge A_i$ であることが保証される．

なお，州 $i$ ($1 \le i \le N$) で獲得した協力者が州 $i$ 以外で演説をすることや，$1$ つの州で同時に $2$ 人以上が演説をすることも可能である．たとえば，ある州で同時に $2$ 人が $x$ 時間演説をした場合，この州の合計演説時間は $2x$ 時間増加する．ただし，演説時間が整数である必要はない．また，州の間を移動する時間は無視できるものとする．

投票日が近いので，理恵さんは目標の $K$ 票をできるだけ早く獲得したい．

州の数と各州の情報が与えられたとき，$K$ 票を集めるまでにかかる時間の最小値を求めるプログラムを作成せよ．

입력

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

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

출력

標準出力に，$K$ 票を集めるまでにかかる時間の最小値を $1$ 行で出力せよ．正解との絶対誤差が $0.01$ 以下であるような答えを出力すれば，正答とみなされる．出力は以下のいずれかの形式でなければならない．

• 整数．（例：123，0，-2022）
• 整数，半角ピリオド，$0$ から $9$ までの数字を並べた列，をその順にスペースなどで区切らず続けた形式．出力する小数点以下の桁数に制限はない．（例：123.4，-123.00，0.00288）

たとえば，1.23456e+05 や 1.23456e5 のような指数表記で出力してはならない．

예제 입력 1

3
3
1 5
2 3
4 5

예제 출력 1

5.500000000000000

以下のような順序で選挙活動を行うと，$5.5$ 時間ですべての州の票を獲得することができる．

1. 理恵さんが州 $2$ で $2$ 時間演説を行い，その州の票を得る．
2. 理恵さんが州 $2$ でさらに $1$ 時間演説を行い，その州の協力者を得る．
3. 理恵さんと協力者 $1$ 人が州 $3$ で $2$ 時間演説を行い，その州の票を得る．
4. 理恵さんと協力者 $1$ 人が州 $1$ で $0.5$ 時間演説を行い，その州の票を得る．

この入力例は小課題 $3, 4, 5, 6, 7$ の制約を満たす．

예제 입력 2

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

예제 출력 2

32.000000000000000

以下のような順序で選挙活動を行うと，$32$ 時間で $4$ 票を獲得することができる．

1. 理恵さんが州 $1$ で $4$ 時間演説を行い，その州の票を得る．
2. 理恵さんが州 $2$ で $11$ 時間演説を行い，その州の票を得る．
3. 理恵さんが州 $3$ で $6$ 時間演説を行い，その州の票を得る．
4. 理恵さんが州 $6$ で $11$ 時間演説を行い，その州の票を得る．

この入力例は小課題 $1, 2, 3, 4, 5, 7$ の制約を満たす．

예제 입력 3

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

예제 출력 3

11.500000000000000

以下のような順序で選挙活動を行うと，$11.5$ 時間で $3$ 票を獲得することができる．

1. 理恵さんが州 $4$ で $7$ 時間演説を行い，その州の票と協力者を得る．
2. 理恵さんが州 $1$ で $4$ 時間演説を行い，その州の票を得る．同時に，協力者 $1$ 人が州 $2$ で $4$ 時間演説を行う．
3. 理恵さんと協力者 $1$ 人が州 $2$ で $0.5$ 時間演説を行い，その州の票を得る．

この入力例は小課題 $2, 3, 4, 5, 7$ の制約を満たす．

예제 입력 4

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

예제 출력 4

62.166666666666664

この入力例は小課題 $3, 4, 5, 7$ の制約を満たす．

예제 입력 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

この入力例は小課題 $4, 5, 7$ の制約を満たす．

제한

• $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$ 점) 追加の制約はない．