题目描述

由于人工智能还没有完全取代商人的工作，你打算做生意赚点钱。具有讽刺意味的是，你决定交易市场上最新的人工智能机器人。

你的生意刚刚起步，因此目前只找到了 $K$ 位朋友作为客户。你还找到了一位供应商，他出售 $N$ 个机器人，编号为 $1$ 到 $N$。你可以买入第 $i$ 个机器人，买入价格为 $a_i$；你决定将它以价格 $b_i$ 卖出。

供应商有一个限制：你必须从他那里购买一段连续编号的机器人。也就是说，如果你要购买机器人 $i$ 和 $j$，那么对于所有 $i\le t\le j$ 的机器人 $t$，你都必须购买。

此外，客户都是你的好友，你已经答应每个人都供应一台机器人。因此，你必须从购入的机器人中恰好卖出 $K$ 台。

你的目标当然是获得尽可能大的利润。如果无法盈利，也要让亏损尽可能小。

请编写程序 trade，计算你能获得的最大利润：你需要购买一段长度至少为 $K$ 的连续机器人，并从其中恰好卖出 $K$ 台。

利润可以为负数。

此外，你的程序还需要判断每个机器人是否可能在某个最大利润方案中被转卖给朋友。

输入格式

第一行包含两个正整数：

$$N\ K$$

分别表示供应商出售的机器人数量和朋友数量。

第二行包含 $N$ 个整数：

$$a_1,a_2,\ldots,a_N$$

表示买入价格。

第三行包含 $N$ 个整数：

$$b_1,b_2,\ldots,b_N$$

表示卖出价格。

输出格式

第一行输出一个整数，表示最大可能利润。

第二行输出一个长度为 $N$ 的 01 字符串。第 $i$ 个字符应为：

• 1：如果第 $i$ 个机器人可以在某个最大利润方案中被转卖；
• 0：否则。

数据范围

• $1 \le N \le 250000$；
• $1 \le K \le N$；
• $1 \le a_i,b_i \le 10^9$。

子任务

子任务	分值	依赖子任务	其他限制
0		-	样例
1	10	0	$N\le 200$
2		0-1	$N\le 6000$
3		-	$K\le 2$
4	25	0,1,3	$K\le 200$
5	45	0-4	无

只有通过该子任务及其依赖子任务的全部测试，才能获得该子任务分数。

评分方式

对于每个子任务：

• 如果所有测试点的第一行最大利润均正确，可获得该子任务 $60\%$ 的分数；
• 如果所有测试点的第一行和第二行均正确，可获得该子任务 $100\%$ 的分数。

样例 1

输入

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

输出

-1
00111

说明

可以买入第 $3,4,5$ 个机器人并全部卖出。买入成本为

$$2+3+6=11,$$

卖出收入为

$$5+2+3=10,$$

因此利润为 $-1$。

可以证明没有其他方案的利润至少为 $-1$。机器人 $3,4,5$ 可以在最大利润方案中被转卖。

样例 2

输入

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

输出

2
10111

说明

可以购买第 $1$ 到第 $3$ 个机器人，并卖出第 $1$ 和第 $3$ 个，利润为 $2$。

也可以通过其他方式达到利润 $2$，例如购买并卖出第 $3,4$ 个机器人，或购买第 $3$ 到第 $5$ 个并卖出第 $3,5$ 个机器人。

因此除了编号为 $2$ 的机器人外，其余机器人都可以在某个最大利润方案中被转卖。