B. Художественное сбалансированное дерево
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Узнав про художественное сбалансированное дерево, Lizhous столкнулся со следующей задачей.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Необходимо выполнить над $$$a$$$ ровно $$$m$$$ операций по порядку. Каждая операция состоит из двух шагов. А именно, в $$$i$$$-й операции вам дано целое число $$$x_i$$$, и вы должны:

  • Сначала выбрать центральный индекс $$$u$$$ и неотрицательную длину $$$y$$$ так, чтобы отрезок $$$[u-y, u+y]$$$ целиком лежал внутри $$$[1, n]$$$ (то есть $$$u - y \ge 1$$$ и $$$u + y \le n$$$). Для каждого $$$1\le i\le y$$$ поменять местами элементы $$$a_{u-i}$$$ и $$$a_{u+i}$$$.
  • Затем пометить элемент на индексе $$$x_i$$$. Если этот элемент уже помечен, ничего не происходит. Обратите внимание, что пометки ставятся на элементы, а не на индексы. Это означает, что если в будущих операциях некоторый элемент будет переставлен с другим, пометка останется на нём.

После выполнения всех $$$m$$$ операций требуется найти минимально возможную сумму всех элементов, которые останутся непомеченными.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — длину массива $$$a$$$ и количество операций.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Третья строка содержит $$$m$$$ целых чисел $$$x_1, x_2, \ldots, x_m$$$ ($$$1 \le x_i \le n$$$) — индексы, которые нужно пометить в каждой операции.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимально возможную сумму непомеченных элементов после выполнения всех операций.

Пример
Входные данные
6
7 4
1 2 3 4 5 6 7
1 2 3 4
7 4
1 -2 3 4 -5 -6 -7
7 6 5 4
7 5
21 -45 234 -8 423 12 -987
6 6 6 6 6
7 5
-21 45 -234 8 -423 -12 987
7 7 7 7 7
7 3
-1 2 -3 4 5 6 7
1 2 3
7 3
-1 -2 -3 -4 -5 -6 -7
1 2 3
Выходные данные
6
-20
-362
-637
2
-25
Примечание

В первом наборе входных данных одна из оптимальных последовательностей операций выглядит так:

  1. Выбрать центр $$$u=4$$$ и длину $$$y=3$$$, тогда $$$a$$$ станет равен $$$[7,6,5,4,3,2,1]$$$. Затем элемент $$$a_1=7$$$ будет помечен.
  2. Выбрать центр $$$u=1$$$ и длину $$$y=0$$$, тогда $$$a$$$ останется равен $$$[7,6,5,4,3,2,1]$$$. Затем элемент $$$a_2=6$$$ будет помечен.
  3. Выбрать центр $$$u=1$$$ и длину $$$y=0$$$, тогда $$$a$$$ останется равен $$$[7,6,5,4,3,2,1]$$$. Затем элемент $$$a_3=5$$$ будет помечен.
  4. Выбрать центр $$$u=1$$$ и длину $$$y=0$$$, тогда $$$a$$$ останется равен $$$[7,6,5,4,3,2,1]$$$. Затем элемент $$$a_4=4$$$ будет помечен.

Непомеченными остаются элементы $$$1$$$, $$$2$$$ и $$$3$$$, поэтому ответ равен $$$1+2+3=6$$$.

Во втором наборе входных данных одна из оптимальных последовательностей операций выглядит так:

  1. Выбрать центр $$$u=4$$$ и длину $$$y=3$$$, тогда $$$a$$$ станет равен $$$[-7,-6,-5,4,3,-2,1]$$$. Затем элемент $$$a_7=1$$$ будет помечен.
  2. Выбрать центр $$$u=5$$$ и длину $$$y=1$$$, тогда $$$a$$$ станет равен $$$[-7,-6,-5,-2,3,4,1]$$$. Затем элемент $$$a_6=4$$$ будет помечен.
  3. Выбрать центр $$$u=1$$$ и длину $$$y=0$$$, тогда $$$a$$$ останется равен $$$[-7,-6,-5,-2,3,4,1]$$$. Затем элемент $$$a_5=3$$$ будет помечен.
  4. Выбрать центр $$$u=5$$$ и длину $$$y=1$$$, тогда $$$a$$$ станет равен $$$[-7,-6,-5,4,3,-2,1]$$$. Затем элемент $$$a_4=4$$$ будет помечен.

Непомеченными остаются элементы $$$-2$$$, $$$-5$$$, $$$-6$$$ и $$$-7$$$, поэтому ответ равен $$$(-2)+(-5)+(-6)+(-7)=-20$$$.