题目描述

给定 $N$ 个加号、$M$ 个减号以及 $N+M+1$ 个整数 $A_1,A_2,⋅⋅⋅,A_{N+M+1}$，小明想知道在所有由这 $N$ 个加号、$M$ 个减号以及 $N+M+1$ 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 "$1\ 2\ 3\ +\ -$"，则 "$2\ 3\ +\ 1\ -$" 这个后缀表达式结果是 4，是最大的。

输入描述

第一行包含两个整数 $N,M$。

第二行包含 $N+M+1$ 个整数 $A_1,A_2,⋅⋅⋅,A_{N+M+1}$。

输出描述

输出一个整，代表答案。

1 1
1 2 3

4

评测用例规模与约定：

对于所有评测用例，$0≤N,M≤100000，-10^9≤A_i≤10^9$。

提示

后缀表达式可以在无括号的情况下实现中缀表达式（日常）有括号的效果，比如：

$ab+c*→(a+b)*c$

$cab+*→c*(a+b)$

$abcd---→a-(b-(c-d))$

借助一个栈，很好实现后缀表达式的计算。遇到数字入栈，遇到运算符出栈并计算。

本题简单理解就是可以自由安排各个数字的计算顺序。（任意摆放运算符以及括号）