시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.6 초 1024 MB244503923.780%

문제

Republic of JOI consists of $N$ states, numbered from $1$ to $N$. In 2022, the presidential election will be held in Republic of JOI. The election will be held in each state. The winner of the election in a state will get the vote of the state.

Rie will run for the president. She is planning to win the election. Her plan is to deliver a speech in order to increase the degree of reliability. After she delivers a speech, the following will happen.

  • If the total time of speech in State $i$ ($1 ≤ i ≤ N$) reaches $A_i$ hours, she will get the vote of State $i$.
  • If the total time of speech in State $i$ ($1 ≤ i ≤ N$) reaches $B_i$ hours, she will get a collaborator from State $i$. After that, the collaborator will be able to deliver a speech in order to increase the total time of speech.
  • It may be the case that Rie cannot get any collaborator from State $i$. In this case, $B_i = -1$. Otherwise, it is guaranteed that $B_i ≥ A_i$ holds.

A collaborator from State $i$ ($1 ≤ i ≤ N$) may deliver a speech outside State $i$. More than one person may deliver a speech in the same state simultaneously. For example, if two people deliver a speech in a state for $x$ hours, the total time of speech in the state will be increased by $2x$ hours. The time of speech needs not be an integer. We will ignore the travel time between states.

Since the election day is coming soon, Rie would like to get $K$ votes as soon as possible.

Given the number of the states and information of each state, write a program which calculate the minimum number of hours required to get $K$ votes.

입력

Read the following data from the standard input. Given values are all integers.

$\begin{align*} & N \\ & K \\ & A_1 \, B_1 \\ & A_2 \, B_2 \\ & \vdots \\ & A_N \, B_N  \end{align*}$

출력

Write one line to the standard output. The output should contain the minimum number of hours required to get $K$ votes. Your solution will be judged correct if the absolute value of the difference from correct answer is less than or equal to $0.01$. The output should be written in one of the following formats.

  • An integer. (Example: 123, 0, -2022)
  • A sequence consisting of an integer, a period, and a sequence of digits between $0$ and $9$. It should not contain separating characters. There is no restriction on the number of digits after the decimal point. (Example: 123.4, -123.00, 0.00288)

The output should not be written in exponential notation. For example, 1.23456e+05 and 1.23456e5 are not allowed.

제한

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

서브태스크

번호배점제한
15

$B_i = -1$ ($1 ≤ i ≤ N$).

25

$B_i = -1$ or $B_i = A_i$ ($1 ≤ i ≤ N$).

311

$N ≤ 7$.

412

$N ≤ 20$.

533

$N ≤ 100$.

611

$K = N$.

723

No additional constraints.

예제 입력 1

3
3
1 5
2 3
4 5

예제 출력 1

5.500000000000000

If the election campaign is held in the following order, Rie will get the vote of every state in $5.5$ hours.

  1. Rie delivers a speech for $2$ hours in State $2$, and gets the vote of State $2$.
  2. Moreover, Rie delivers a speech for one hour in State $2$, and gets a collaborator from State $2$.
  3. Rie and the collaborator deliver a speech for $2$ hours in State $3$, and Rie gets the vote of State $3$.
  4. Rie and the collaborator deliver a speech for $0.5$ hour in State $1$, and Rie gets the vote of State $1$.

This sample input satisfies the constraints of Subtasks 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

If the election campaign is held in the following order, Rie will get $4$ votes in $32$ hours.

  1. Rie delivers a speech for $4$ hours in State $1$, and gets the vote of State $1$.
  2. Rie delivers a speech for $11$ hours in State $2$, and gets the vote of State $2$.
  3. Rie delivers a speech for $6$ hours in State $3$, and gets the vote of State $3$.
  4. Rie delivers a speech for $11$ hours in State $6$, and gets the vote of State $6$.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 7.

예제 입력 3

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

예제 출력 3

11.500000000000000

If the election campaign is held in the following order, Rie will get $3$ votes in $11.5$ hours.

  1. Rie delivers a speech for $7$ hours in State $4$, and gets the vote of State $4$ and a collaborator from State $4$.
  2. Rie delivers a speech for $4$ hours in State $1$, and gets the vote of State $1$. At the same time, the collaborator delivers a speech for $4$ hours in State $2$.
  3. Rie and the collaborator deliver a speech for $0.5$ hour in State $2$, and Rie gets the vote of State $2$.

This sample input satisfies the constraints of Subtasks 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

This sample input satisfies the constraints of Subtasks 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

This sample input satisfies the constraints of Subtasks 4, 5, 7.

채점 및 기타 정보

  • 예제는 채점하지 않는다.