{"raw_statement":[{"iden":"background","content":"译自 CEOI2023 Day2 T1 [Trade](https://www.ceoi2023.de/wp-content/uploads/2023/09/4-trade.pdf)。"},{"iden":"statement","content":"有 $n$ 个机器人排成一排，第 $i$ 个机器人的购买价是 $c_i$ 欧元，卖出价是 $s_i$ 欧元。\n\n给定 $1\\le k\\le n$，你需要购买一段长度至少为 $k$ 的区间中所有的机器人，然后选择其中的恰好 $k$ 个机器人来卖出。\n\n你需要求出：\n1. 你能够得到的最大收益；\n2. 在收益最大化的前提下，哪些机器人可以在某种最优方案中被卖出。"},{"iden":"input","content":"第一行包含两个整数 $n,k$。\n\n第二行 $n$ 个正整数 $c_1,\\dots,c_n$。\n\n第三行 $n$ 个正整数 $s_1,\\dots,s_n$。"},{"iden":"output","content":"第一行输出一个整数表示最大收益。\n\n第二行输出一个 $01$ 串，第 $i$ 位输出 $1$ 表示第 $i$ 个机器人可以在某种最优方案中被卖出，反之第 $i$ 位输出 $0$。"},{"iden":"note","content":"样例一中最优方案是购买第 $3\\sim 5$ 个机器人然后将它们卖出，但仍然会亏损 $1$ 欧元。\n\n样例二中最大收益为 $2$ 欧元，可以购买 $1,2,3$ 并卖出 $1,3$，也可以购买 $3,4$ 并卖出 $3,4$，也可以购买 $3,4,5$ 并卖出 $3,5$，因此 $1,3,4,5$ 都有可能在某种最优方案中被卖出，输出 `10111`。\n\n### 数据规模与约定\n\n对于全部数据，$1\\le k\\le n \\le 250000$，$1\\le c_i,s_i\\le 10^9$。\n\n- Subtask 1（5+5 points）：$n \\le 200$。\n- Subtask 2（5+5 points）：$n \\le 6000$。\n- Subtask 3（5+5 points）：$k=2$。\n- Subtask 4（10+15 points）：$k\\le 200$。\n- Subtask 5（25+20 points）：无特殊限制。\n\n在每个子任务中，如果第一行的输出正确，可以获得子任务前半部分的分数，如果第二行的输出也正确，可以获得子任务全部的分数。"}],"translated_statement":null,"sample_group":[["5 3\n3 5 2 3 6\n2 1 5 2 3","-1\n00111"],["5 2\n1 6 1 5 2\n4 1 6 2 4","2\n10111"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}