每个玩过《割绳子》的人都非常清楚游戏玩法是如何组织的。游戏中的所有级别都分为盒子。最初只有一个包含某些级别的盒子可用。玩家应该完成关卡才能获得星星,收集星星会打开带有关卡的新盒子。
想象一下您是第一次玩割绳子。目前您只有第一个盒子的级别(顺便说一下,它被称为“纸板箱”)。每个级别由两个整数来表征:ai - 完成一颗星的级别需要多长时间,bi - 完成两颗星的级别需要多长时间(ai < bi)。
您想尽快打开下一个盒子。因此,您需要至少获得 w 颗星。如何让它发生?请注意,该级别只能通过一次:一颗星或两颗星。您不一定需要通过所有级别。
输入
第一行包含两个整数 n 和 w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — 第一个盒子中的级别数以及打开另一个盒子所需的星星数。接下来的 n 行每一行都包含两个整数 ai 和 bi (1 ≤ ai < bi ≤ 109)——第 i 层的属性。
输出
在第一行打印整数 t — 打开下一个框所需的最短时间。
在下一行中,打印 n 个不带空格的数字 — 最佳场景的描述:
- 如果需要通过第i关获得一颗星,则第i位数字应等于1;
- 如果需要通过第i关两颗星,则第i位数字应等于2;
- 如果您根本不需要通过第 i 级,则第 i 位数字应等于 0。
示例
输入 #1
2 3 1 2 1 2
输出 #1
3 12
输入 #2
5 3 10 20 5 10 10 20 6 9 25 30
输出 #2
14 01020
注意
在第一个测试样本中,答案 21 也被假定为正确。