题目描述

给定一个长度为 $n$ 的序列，Alice 和 Bob 交替操作一共 $k$ 次，第 $i$ 次当前操作的人必须选一个 $-x_i \sim x_i$ 的整数把它插在序列开头或结尾，Alice 先手（也就是说 $i$ 为奇数时由 Alice 来插入一个 $-x_i\sim x_i$ 的整数，$i$ 为偶数时由 Bob 来插入一个 $-x_i\sim x_i$ 的整数）。

记最终的序列为 $a_1,a_2,\dots,a_{n+k}$，则得分为 $\sum_{i=1}^{n+k} (-1)^{i-1}a_i$。Alice 希望得分最大，Bob 希望得分最小。在两人都采取最优策略的情况下，求最终得分。

输入格式

第一行两个正整数 $n,k$ 表示初始序列长度以及操作次数。

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示初始的序列。

接下来一行 $k$ 个非负整数，第 $i$ 个表示 $x_i$。

输出格式

一行一个整数表示答案。

2 2
1 3
2 2

-2

提示

本题采用捆绑测试

对于所有数据，保证 $1\le n,k\le 2\times 10^5$，$0\le |a_i|,x_i\le 10^9$。

本题测试点较多，为了保证评测速度，本题时限 500ms，保证时限在 std 所用最大时间的 5 倍以上。