7065 - 后缀表达式

通过次数

54

提交次数

260

时间限制 : 1 秒
内存限制 : 256 MB

给定 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,是最大的。 

输入

第一行包含两个整数 NM。 

第二行包含 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。

来源

第十届蓝桥杯大赛软件类省赛 C/C++ 大学 B 组