给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$ 和由 $$$m$$$ 正整数组成的 $$$B$$$ 集合,使得 $$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$ 对于 $$$1\le i\le m$$$,其中 $$$b_i$$$ 是$$$B$$$ 的 $$$i$$$ 个元素。
您可以对$$$a$$$进行以下操作:
1. 选择一些$$$x$$$,使$$$x$$$ 出现在$$$B$$$ 中。
2. 从大小为 $$$x$$$ 的数组 $$$a$$$ 中选择一个区间,并将区间中的每个元素乘以 $$$-1$$$。形式上,选择 $$$l$$$ 和 $$$r$$$,使得 $$$1\leq l\leq r \leq n$$$ 和 $$$r-l+1=x$$$,然后为每个 $$$i$$$ 分配 $$$a_i:=-a_i$$$,使得 $$$l\leq i\leq r$$$。
考虑以下示例,令 $$$a=[0,6,-2,1,-4,5]$$$ 和 $$$B=\{1,2\}$$$:
1. $$$[0,6,-2,-1,4,5]$$$是在选择尺寸$$$2$$$和$$$l=4$$$、$$$r=5$$$后得到的。
2. $$$[0,6,2,-1,4,5]$$$是选择尺寸$$$1$$$和$$$l=3$$$、$$$r=3$$$后得到的。
找到在应用此类操作任意次(可能为零)后可以获得的最大$$$\sum\limits_{i=1}^n {a_i}$$$。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\leq n \leq 10^6$$$, $$$1 \leq m \leq \lfloor \frac{n}{2} \rfloor$$$) — 分别是 $$$a$$$ 和 $$$B$$$ 的元素数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\leq a_i \leq 10^9$$$)。
每个测试用例的第三行包含 $$$m$$$ 不同的正整数 $$$b_1,b_2,\ldots,b_m$$$ ($$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$) — 集合 $$$B$$$ 中的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印一个整数 - 应用此类操作任意次后所有 $$$a_i$$$ 的最大可能总和。
示例
输入 #1
3 6 2 0 6 -2 1 -4 5 1 2 7 1 1 -1 1 -1 1 -1 1 2 5 1 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1
输出 #1
18 5 5000000000
注意
在第一个测试中,您可以应用操作$$$x=1$$$、$$$l=3$$$、$$$r=3$$$,以及操作$$$x=1$$$、$$$l=5$$$、$$$r=5$$$,则数组变为$$$[0, 6, 2, 1, 4, 5]$$$。
在第二个测试中,可以应用操作 $$$x=2$$$, $$$l=2$$$, $$$r=3$$$,数组变为 $$$[1, 1, -1, -1, 1, -1, 1]$$$,然后应用操作 $$$x=2$$$, $$$l=3$$$, $$$r=4$$$,并且数组变为 $$$[1, 1, 1, 1, 1, -1, 1]$$$。没有办法获得超过 $$$5$$$ 的总和。