由于你的艺术大盗生涯远没有你预想的那么光鲜，你将目光投向了一个新的目标：你想在今年的 CEOI 上偷走一枚奖牌！到目前为止，你的邪恶计划进展顺利：科学委员会仍然对你制造的石油短缺感到困惑，并立即落入了你伪造的黑客攻击陷阱中。当他们让你进入秘密总部协助规划重新评测时，你轻易地偷到了存放奖牌的保险箱密码……

然而，你计划的下一阶段需要一名助手，而你现在没有足够的钱来雇佣。幸运的是，你刚刚发现了一个解决这个问题的机会。你在柏林偶然发现的一家商店出售 $N$ 台可编程吸尘机器人，编号从 $1$ 到 $N$。第 $i$ 台机器人的成本为 $c_i$ 欧元。不幸的是，店主只会卖给你一段完整的、连续的机器人：如果你想购买第 $i$ 台和第 $j$ 台机器人，那么你必须购买所有满足 $i \le k \le j$ 的机器人 $k$。

由于你的参赛选手同伴非常喜欢机器人，你承诺卖给他们其中的 $K$ 台机器人（$1 \le K \le N$）。他们会为第 $i$ 台机器人支付 $s_i$ 欧元，你希望在此过程中获得丰厚的利润。

编写一个程序，完成以下任务： 计算通过购买一段至少包含 $K$ 台机器人的区间，并从中卖出恰好 $K$ 台机器人所能获得的最大利润，以及 确定在获得最大利润的交易中，哪些机器人可能被卖给其他参赛选手。†

输入格式

输入的第一行包含上述数字 $N$ 和 $K$。第二行包含 $N$ 个整数 $c_1, \dots, c_N$。最后，第三行包含 $N$ 个整数 $s_1, \dots, s_N$。

输出格式

你的程序应输出两行。第一行应包含一个整数，即你可以获得的最大利润。第二行应输出一个长度为 $N$ 的二进制字符串：如果第 $i$ 台机器人可能出现在某个最大利润的交易中，则第 $i$ 个字符应为 $1$，否则为 $0$。

数据范围

我们始终有 $1 \le N \le 250\,000$ 且 $1 \le c_i, s_i \le 10^9$。

• 子任务 1（5 + 5 分）：$N \le 200$
• 子任务 2（5 + 5 分）：$N \le 6\,000$
• 子任务 3（5 + 5 分）：$K = 2$
• 子任务 4（10 + 15 分）：$K \le 200$
• 子任务 5（25 + 20 分）：无额外限制

说明

在所有子任务中，你可以获得括号中所示的部分分数： 第一个数字表示如果你的程序正确计算出最大利润所获得的积分。 第二个数字表示如果你的程序正确计算出完整输出所获得的额外积分。

样例

样例输入 1

5 3
3 5 2 3 6
2 1 5 2 3

样例输出 1

-1
00111

样例输入 2

5 2
1 6 1 5 2
4 1 6 2 4

样例输出 2

2
10111

说明

在第一个样例中，你可以购买第三到第五台机器人，并将这三台全部卖给你的同伴。这花费了你 $2 + 3 + 6 = 11$ 欧元，而参赛选手只会为你支付 $5 + 2 + 3 = 10$ 欧元，因此你亏损了 $1$ 欧元。如果你购买任何其他机器人区间，你亏损的钱会更多。

在第二个样例中，你可以购买第一到第三台机器人，并卖出第一和第三台给你的同伴。这花费了你 $8$ 欧元，而参赛选手会支付 $10$ 欧元，因此你的利润是 $2$ 欧元。没有其他机器人区间能给你更高的利润。然而，你也可以购买第三和第四台机器人并将它们全部卖出，或者购买第三到第五台机器人并卖出第三和第五台。在这两种情况下，你的利润也都是 $2$ 欧元，因此除了第二台机器人外，所有机器人都可以成为最大利润交易的一部分。

• 显然，问题出在艺术品上，而不是盗窃行为上。 † 毕竟，你可能会发现你留下的机器人还有些用处……