Description

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.

Input Format

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 Format

Output one integer, which is the answer.

1 1
1 2 3

4

Hint

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