P8683 [Lanqiao Cup 2019 NOI Qualifier B] Suffix Expression

Given $N$ plus signs, $M$ minus signs, and $N+M+1$ integers $A_1,A_2,\cdots,A_{N+M+1}$, Xiaoming wants to know which legal postfix expression formed by these $N$ plus signs, $M$ minus signs, and $N+M+1$ integers has the maximum value. Please output this maximum value. For example, using `1 2 3 + -`, the postfix expression `2 3 + 1 -` has value $4$, which is the maximum.

The first line contains two integers $N$ and $M$. The second line contains $N+M+1$ integers $A_1,A_2,\cdots,A_{N+M+1}$.

Output one integer, which is the answer.

For all test cases, $0 \le N,M \le 10^5$, $-10^9 \le A_i \le 10^9$. Lanqiao Cup 2019 Provincial Contest Group B, Problem I. Translated by ChatGPT 5