Background

Translated from CEOI 2023 Day 2 T1 Trade.

Problem Description

There are $n$ robots in a line. The purchase price of the $i$-th robot is $c_i$ euros, and the selling price is $s_i$ euros.

Given $1 \le k \le n$, you need to buy all robots in some interval of length at least $k$, and then choose exactly $k$ robots among them to sell.

You need to find:

1. The maximum profit you can obtain.
2. Under the condition that the profit is maximized, which robots can be sold in some optimal plan.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ positive integers $c_1, \dots, c_n$.

The third line contains $n$ positive integers $s_1, \dots, s_n$.

Output Format

The first line outputs one integer, the maximum profit.

The second line outputs a 01 string. The $i$-th character should be 1 if the $i$-th robot can be sold in some optimal plan; otherwise output 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

Hint

In sample 1, the optimal plan is to buy robots $3 \sim 5$ and then sell them, but you still lose $1$ euro.

In sample 2, the maximum profit is $2$ euros. You can buy $1, 2, 3$ and sell $1, 3$. You can also buy $3, 4$ and sell $3, 4$. You can also buy $3, 4, 5$ and sell $3, 5$. Therefore, robots $1, 3, 4, 5$ may be sold in some optimal plan, so output 10111.

Constraints

For all testdata, $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): No special constraints.

In each subtask, if the first line of the output is correct, you can get the first half of the subtask score. If the second line is also correct, you can get the full score of the subtask.

Translated by ChatGPT 5