P9051 [PA 2021] Exhibition

You are given two sequences $a$ and $b$ of length $n$. You need to construct a sequence $c$ as follows: - Choose $k$ indices $i$ and set $c_i \leftarrow a_i$. - For all other $i$, set $c_i \leftarrow b_i$. Find the minimum possible value of the maximum subarray sum of sequence $c$, and output one valid construction.

The first line contains two integers $n, k$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$. The third line contains $n$ integers $b_1, b_2, \cdots, b_n$.

The first line contains one integer, the minimum possible value of the maximum subarray sum of sequence $c$. The second line contains a string $s$ of length $n$. If $c_i \leftarrow a_i$, then $s_i = \text{A}$; otherwise, $s_i = \text{B}$. **If there are multiple solutions, output any one of them.**

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $0 \leq k \leq n$, and $-10^9 \leq a_i, b_i \leq 10^9$. Translated by ChatGPT 5