题目描述

题目译自 CEOI 2023 Day2 T1「Tricks of the Trade」

由于你的艺术品窃贼生涯显然没有你所期望的那么风光，所以你把目光投向了一个新的目标：你想在今年的 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,\ldots,c_N$。

第三行包含 $N$ 个整数 $s_1,\ldots,s_N$。

输出格式

你的程序应输出两行。第一行包含一个整数，表示你可以达到的最大利润。第二行输出一个长为 $N$ 的 01 串：如果你可以在交易中卖出机器人 $i$ 以获得最大利润，则第 $i$ 个字符为 1，否则为 0。

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

-1
00111

在第一个样例，你可以买第三个到第五个机器人，并且把这三个机器人全部卖给你的朋友。这将花费你 $2+3+6=11$ 欧元，而这些选手只会付你 $5+2+3=10$ 欧元，所以你赔了 $1$ 欧元。如果你买任意其他的段，你会赔更多的钱。

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

2
10111

在第二个样例，你可以买从第一到第三个机器人，并且卖出第一和第三个机器人。这将花费你 $8$ 欧元，选手会付你 $10$ 欧元，所以你的利润是 $2$ 欧元。没有其他段会让你挣得更多。但是，你也可以买下第三和第四个机器人，并且把它们两个卖掉，或者买第三个到第五个机器人并卖出第三和第五个机器人，你的利润也会是 $2$ 欧元。所以除了第二个机器人之外的所有机器人都可以是获得最大利润的交易中的一部分。

数据范围与提示

对于所有数据，总有 $1\le N\le 2.5\times 10^5,1\le c_i,s_i\le 10^9$。

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N\le 200$	$5+5$
$2$	$N\le 6\ 000$
$3$	$K=2$
$4$	$K\le 200$	$10+15$
$5$	无附加限制	$25+20$

对于所有子任务，你可以获得如「分值」一栏所示的部分分：

• 第一个数表示如果你的程序正确计算了最大利润所能获得的分值。
• 第二个数表示如果你的程序输出全部正确所能获得的附加分值。