题目描述

注意 本题包含special judge

每个玩过《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$。

输入输出样例 #1

输入 #1

2 3
1 2
1 2

输出 #1

3
12

输入输出样例 #2

输入 #2

5 3
10 20
5 10
10 20
6 9
25 30

输出 #2

14
01020

说明/提示

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