AT_joi2022ho_c.選挙で勝とう (Let's Win the Election)

JOI 国由 $N$ 个州组成，每个州编号为 $1$ 到 $N$。2022 年，JOI 国将举办总统选举。在这次选举中，每个州都会进行投票，获胜的候选人将获得该州分配的 $1$ 票。

理惠打算通过演讲提升自己在各州的信任度，从而赢得选举。具体来说，演讲会产生如下效果：

• 在州 $i$（$1 \leq i \leq N$）的总演讲时间达到 $A_i$ 小时时，可以获得该州分配的 $1$ 票。
• 在州 $i$（$1 \leq i \leq N$）的总演讲时间达到 $B_i$ 小时时，可以获得 $1$ 名协助者。获得的协助者可以继续进行演讲，增加总演讲时间。
• 但有些州无法获得协助者，这种情况下 $B_i = -1$。除此之外，保证 $B_i \geq A_i$。

此外，从州 $i$ 获得的协助者可以在其他州进行演讲，也可以在同一个州同时有多个人进行演讲。例如，如果某州有 $2$ 个人同时演讲 $x$ 小时，则该州的总演讲时间会增加 $2x$ 小时。演讲时间可以不是整数。州与州之间的移动时间可以忽略不计。

由于投票日临近，理惠希望尽快获得目标的 $K$ 票。

给定各州的信息，请编写程序求出获得 $K$ 票所需的最短时间。

输入通过标准输入给出，格式如下。所有输入均为整数。

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

请输出获得 $K$ 票所需的最短时间，输出一行。只要你的答案与标准答案的绝对误差不超过 $0.01$，即可视为正确。输出必须为以下两种格式之一：

• 整数。（如：123，0，-2022）
• 整数、小数点、若干数字，三者不加空格连续输出。（如：123.4，-123.00，0.00288）

例如，不能输出如 1.23456e+05 或 1.23456e5 这样的科学计数法。

限制条件

• $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$ 或 $B_i = -1$（$1 \leq i \leq N$）。

子任务

1.（5 分）$B_i = -1$（$1 \leq i \leq N$）。
2.（5 分）$B_i = -1$ 或 $B_i = A_i$（$1 \leq i \leq N$）。
3.（11 分）$N \leq 7$。
4.（12 分）$N \leq 20$。
5.（33 分）$N \leq 100$。
6.（11 分）$K = N$。
7.（23 分）无额外限制。

---

样例解释 1

按如下顺序进行选举活动，可以在 $5.5$ 小时内获得所有州的选票。

1. 理惠在州 $2$ 演讲 $2$ 小时，获得该州选票。
2. 理惠在州 $2$ 再演讲 $1$ 小时，获得该州协助者。
3. 理惠和 $1$ 名协助者在州 $3$ 演讲 $2$ 小时，获得该州选票。
4. 理惠和 $1$ 名协助者在州 $1$ 演讲 $0.5$ 小时，获得该州选票。

该输入样例满足子任务 $3, 4, 5, 6, 7$ 的限制。

---

样例解释 2

按如下顺序进行选举活动，可以在 $32$ 小时内获得 $4$ 票。

1. 理惠在州 $1$ 演讲 $4$ 小时，获得该州选票。
2. 理惠在州 $2$ 演讲 $11$ 小时，获得该州选票。
3. 理惠在州 $3$ 演讲 $6$ 小时，获得该州选票。
4. 理惠在州 $6$ 演讲 $11$ 小时，获得该州选票。

该输入样例满足子任务 $1, 2, 3, 4, 5, 7$ 的限制。

---

样例解释 3

按如下顺序进行选举活动，可以在 $11.5$ 小时内获得 $3$ 票。

1. 理惠在州 $4$ 演讲 $7$ 小时，获得该州选票和协助者。
2. 理惠在州 $1$ 演讲 $4$ 小时，获得该州选票。同时，$1$ 名协助者在州 $2$ 演讲 $4$ 小时。
3. 理惠和 $1$ 名协助者在州 $2$ 演讲 $0.5$ 小时，获得该州选票。

该输入样例满足子任务 $2, 3, 4, 5, 7$ 的限制。

---

样例解释 4

该输入样例满足子任务 $3, 4, 5, 7$ 的限制。

---

样例解释 5

该输入样例满足子任务 $4, 5, 7$ 的限制。

由 ChatGPT 4.1 翻译