D. Переверни отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел, и множество $$$B$$$, состоящее из $$$m$$$ положительных целых чисел таких, что $$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$ при $$$1\le i\le m$$$, где $$$b_i$$$ — $$$i$$$-й элемент $$$B$$$.

Вы можете выполнять следующую операцию с $$$a$$$:

  1. Выбрать некоторый $$$x$$$ такой, что $$$x$$$ содержится в $$$B$$$.
  2. Выбрать подмассив $$$a$$$ размера $$$x$$$ и умножить на $$$-1$$$ каждый элемент этого подмассива. Формально, выбрать $$$l$$$ и $$$r$$$ такие, что $$$1\leq l\leq r \leq n$$$ и $$$r-l+1=x$$$, и затем присвоить $$$a_i:=-a_i$$$ для всех $$$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$$$, которую можно получить, применяя описанную операцию неограниченное количество раз.

Пример
Входные данные
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
Выходные данные
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$$$.