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 翻译