CF1630D.Flipping Range

You are given an array $a$ of $n$ integers and a set $B$ of $m$ positive integers such that $1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$ for $1\le i\le m$, where $b_i$ is the $i$-th element of $B$.

You can make the following operation on $a$:

1. Select some $x$ such that $x$ appears in $B$.
2. Select an interval from array $a$ of size $x$ and multiply by $-1$ every element in the interval. Formally, select $l$ and $r$ such that $1\leq l\leq r \leq n$ and $r-l+1=x$, then assign $a_i:=-a_i$ for every $i$ such that $l\leq i\leq r$.

Consider the following example, let $a=[0,6,-2,1,-4,5]$ and $B={1,2}$:

1. $[0,6,-2,-1,4,5]$ is obtained after choosing size $2$ and $l=4$, $r=5$.
2. $[0,6,2,-1,4,5]$ is obtained after choosing size $1$ and $l=3$, $r=3$.

Find the maximum $\sum\limits_{i=1}^n {a_i}$ you can get after applying such operation any number of times (possibly zero).

给你一个包含 $n$ 个整数的数组 $a$，以及一个包含 $m$ 个正整数的集合 $B$，满足对所有 $1 \le i \le m$，有 $1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$，其中 $b_i$ 表示集合 $B$ 中的第 $i$ 个元素。

你可以在数组 $a$ 上执行如下操作：

1. 选择某个 $x$，使得 $x$ 属于集合 $B$；
2. 在数组 $a$ 中选取一个长度为 $x$ 的连续子区间，并将该区间内每个元素乘以 $-1$。形式化地说，选择下标 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$ 且 $r - l + 1 = x$，然后对所有满足 $l \leq i \leq r$ 的 $i$，令 $a_i := -a_i$。

考虑如下示例：设 $a = [0,6,-2,1,-4,5]$，$B = \{1,2\}$：

1. 若选择长度 $x = 2$，并取 $l = 4$、$r = 5$，则得到 $[0,6,-2,-1,4,5]$；
2. 若选择长度 $x = 1$，并取 $l = 3$、$r = 3$，则得到 $[0,6,2,-1,4,5]$。

求在执行上述操作任意次数（包括零次）后，所能达到的最大值 $\sum\limits_{i=1}^n {a_i}$。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2\leq n \leq 10^6$, $1 \leq m \leq \lfloor \frac{n}{2} \rfloor$) — the number of elements of $a$ and $B$ respectively.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\leq a_i \leq 10^9$).

The third line of each test case contains $m$ distinct positive integers $b_1,b_2,\ldots,b_m$ ($1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$) — the elements in the set $B$.

It's guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case print a single integer — the maximum possible sum of all $a_i$ after applying such operation any number of times.

对于每个测试用例，输出一个整数——在任意次数执行该操作后，所有 $a_i$ 的和的最大可能值。

In the first test, you can apply the operation $x=1$, $l=3$, $r=3$, and the operation $x=1$, $l=5$, $r=5$, then the array becomes $[0, 6, 2, 1, 4, 5]$.

In the second test, you can apply the operation $x=2$, $l=2$, $r=3$, and the array becomes $[1, 1, -1, -1, 1, -1, 1]$, then apply the operation $x=2$, $l=3$, $r=4$, and the array becomes $[1, 1, 1, 1, 1, -1, 1]$. There is no way to achieve a sum bigger than $5$.

在第一个测试用例中，你可以执行操作 $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$ 的方法。