CF436E.Cardboard Box

Everyone who has played Cut the Rope knows full well how the gameplay is organized. All levels in the game are divided into boxes. Initially only one box with some levels is available. Player should complete levels to earn stars, collecting stars opens new box with levels.

Imagine that you are playing Cut the Rope for the first time. Currently you have only the levels of the first box (by the way, it is called "Cardboard Box"). Each level is characterized by two integers: a__i — how long it takes to complete the level for one star, b__i — how long it takes to complete the level for two stars (a__i < b__i).

You want to open the next box as quickly as possible. So, you need to earn at least w stars. How do make it happen? Note that the level can be passed only once: either for one star or for two. You do not necessarily need to pass all the levels.

所有玩过《割绳子》（Cut the Rope）的玩家都十分清楚游戏的玩法机制。游戏中的所有关卡被划分为若干个“盒子”（box）。初始时，仅有一个包含若干关卡的盒子开放。玩家需完成关卡以获取星星，收集足够数量的星星后，新的关卡盒子才会解锁。

假设你第一次玩《割绳子》。当前你仅能访问第一个盒子中的关卡（顺便一提，它被称为“纸板盒”）。每个关卡由两个整数刻画：$a_i$ 表示以一颗星为目标完成该关卡所需的时间，$b_i$ 表示以两颗星为目标完成该关卡所需的时间（满足 $a_i < b_i$）。

你希望尽快解锁下一个盒子。因此，你需要至少获得 $w$ 颗星星。你该如何实现？注意：每个关卡只能通关一次——即只能选择获得一颗星或两颗星，不可重复挑战；你也不必通关所有关卡。

The first line contains two integers n and w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2_n_) — the number of levels in the first box and the number of stars you need to open another box. Each of the following n lines contains two integers a__i and b__i (1 ≤ a__i < b__i ≤ 109) — the attributes of the i-th level.

第一行包含两个整数 $n$ 和 $w$（$1 ≤ n ≤ 3·10^5$；$1 ≤ w ≤ 2n$）—— 分别表示第一个宝箱中的关卡数量以及开启另一个宝箱所需的星星数量。接下来的 $n$ 行中，每行包含两个整数 $a_i$ 和 $b_i$（$1 ≤ a_i < b_i ≤ 10^9$）—— 表示第 $i$ 关的属性。

In the first line print integer t — the minimum time you need to open the next box.

In the next line, print n digits without spaces — the description of the optimal scenario:

• if you need to pass the i-th level for one star, the i-th digit should equal 1;
• if you need to pass the i-th level for two stars, the i-th digit should equal 2;
• if you do not need to pass the i-th level at all, the i-th digit should equal 0.

第一行输出整数 $t$ —— 打开下一个宝箱所需的最短时间。

第二行输出 $n$ 个数字（不带空格）—— 描述最优策略：

• 若需通过第 $i$ 关获得一颗星，则第 $i$ 位数字应为 1；
• 若需通过第 $i$ 关获得两颗星，则第 $i$ 位数字应为 2；
• 若完全无需通过第 $i$ 关，则第 $i$ 位数字应为 0。

In the first test sample, answer 21 is also assumed correct.

在第一个测试样例中，答案 21 也被视为正确。