题目背景

译自 CEOI2023 Day2 T1 Trade。

题目描述

有 $n$ 个机器人排成一排，第 $i$ 个机器人的购买价是 $c_i$ 欧元，卖出价是 $s_i$ 欧元。

给定 $1\le k\le n$，你需要购买一段长度至少为 $k$ 的区间中所有的机器人，然后选择其中的恰好 $k$ 个机器人来卖出。

你需要求出：

1. 你能够得到的最大收益；
2. 在收益最大化的前提下，哪些机器人可以在某种最优方案中被卖出。

输入格式

第一行包含两个整数 $n,k$。

第二行 $n$ 个正整数 $c_1,\dots,c_n$。

第三行 $n$ 个正整数 $s_1,\dots,c_n$。

输出格式

第一行输出一个整数表示最大收益。

第二行输出一个 $01$ 串，第 $i$ 位输出 $1$ 表示第 $i$ 个机器人可以在某种最优方案中被卖出，反之第 $i$ 位输出 $0$。

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

-1
00111

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

2
10111

提示

样例一中最优方案是购买第 $3\sim 5$ 个机器人然后将它们卖出，但仍然会亏损 $1$ 欧元。

样例二中最大收益为 $2$ 欧元，可以购买 $1,2,3$ 并卖出 $1,3$，也可以购买 $3,4$ 并卖出 $3,4$，也可以购买 $3,4,5$ 并卖出 $3,5$，因此 $1,3,4,5$ 都有可能在某种最优方案中被卖出，输出 10111。

数据规模与约定

对于全部数据，$1\le k\le n \le 250000$，$1\le c_i,s_i\le 10^9$。

• Subtask 1（5+5 points）：$n \le 200$。
• Subtask 2（5+5 points）：$n \le 6000$。
• Subtask 3（5+5 points）：$k=2$。
• Subtask 4（10+15 points）：$k\le 200$。
• Subtask 5（25+20 points）：无特殊限制。

在每个子任务中，如果第一行的输出正确，可以获得子任务前半部分的分数，如果第二行的输出也正确，可以获得子任务全部的分数。