24476번 - Let’s Win the Election 서브태스크스페셜 저지다국어

문제

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 2ドルx$ 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$).

서브태스크

힌트