CF436E Cardboard Box

每个玩过《Cut the Rope》的人都很清楚这款游戏的玩法。游戏中的所有关卡被划分为若干“箱子”。最开始，玩家只能游玩一个箱子里的若干关卡。玩家需要通关关卡获得星星，收集到足够数量的星星后就能解锁新的箱子和关卡。 想象你第一次玩《Cut the Rope》。现在你只解锁了第一个箱子的关卡（顺便提一下，这个箱子叫作 “Cardboard Box”）。每个关卡都有两个整数属性：$a_i$ 表示以最快速只获得一颗星所需的时间，$b_i$ 表示以最快速获得两颗星所需的时间（$a_i < b_i$）。 你想以尽可能快的速度解锁下一个箱子，为此你需要获得至少 $w$ 颗星。那么你该如何安排通关顺序以最快达成目标？注意：每个关卡只能通关一次——要么获得一颗星，要么获得两颗星。并不是所有关卡都需要被通关。

第一行包含两个整数 $n$ 和 $w$ $(1 \le n \le 3 \cdot 10^{5};\ 1 \le w \le 2n)$——第一个箱子中的关卡数和解锁下一个箱子所需的星星数。接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(1 \le a_i < b_i \le 10^9)$——第 $i$ 个关卡的属性。

第一行输出整数 $t$——解锁下一个箱子所需的最少时间。 第二行输出 $n$ 个数字（不含空格），表示最优方案： - 如果第 $i$ 个关卡只通关并获得一颗星，则第 $i$ 个数字为 $1$； - 如果第 $i$ 个关卡通关并获得两颗星，则第 $i$ 个数字为 $2$； - 如果第 $i$ 个关卡未被通过，则第 $i$ 个数字为 $0$。

对于第一个测试样例，输出 $21$ 也视为正确答案。 由 ChatGPT 5 翻译