Maximize Robot Trading Profit

You have n robots lined up in a row. The i-th robot has a purchase cost of \(c_i\) euros and a selling price of \(s_i\) euros.

Given an integer \(k\) satisfying \(1 \le k \le n\), you are allowed to purchase all robots in any contiguous segment (interval) of the line whose length is at least \(k\). Then, from the purchased robots you must choose exactly \(k\) robots to sell. In an interval \([L,R]\) with \(R-L+1\ge k\), your profit is defined as:

[ \text{Profit} = \Bigl( \sum_{\text{selected } i \in [L,R]} s_i \Bigr) - \Bigl( \sum_{i=L}^{R} c_i \Bigr). ]

Your task is to compute:

1. The maximum profit that can be obtained.
2. Under the condition of maximum profit, determine which robots can be sold in some optimal solution. Output a binary string of length \(n\) where the \(i\)-th character is '1' if the \(i\)-th robot can be sold in some optimal solution, and '0' otherwise.

Note: In any chosen interval, the optimal strategy is to sell the \(k\) robots with the largest selling prices. If there are ties, any robot with a selling price equal to the \(k\)-th highest value is considered sellable (since you can choose a subset of them to fill the \(k\) selling slots).

inputFormat

The input consists of the following:

• The first line contains two integers \(n\) and \(k\) (number of robots and number to sell) separated by a space.
• The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\) representing the purchase costs.
• The third line contains \(n\) integers \(s_1, s_2, \dots, s_n\) representing the selling prices.

outputFormat

The output should contain two lines:

• The first line contains a single integer: the maximum profit.
• The second line contains a binary string of length \(n\). The \(i\)-th character is '1' if the i-th robot can be sold in some optimal solution, and '0' otherwise.

sample

5 2
3 2 5 2 4
5 3 6 3 5

3
11000