C. Раздражающая игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целочисленных массива $$$a$$$ и $$$b$$$, оба длиной $$$n$$$, и общее количество ходов $$$k$$$.

Алиса и Боб играют в игру, поочередно изменяя массив $$$a$$$. Алиса ходит первой. Игра длится ровно $$$k$$$ ходов.

В свой ход игрок должен выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и выполнить одно из следующих действий:

  • Прибавить: Увеличить $$$a_i$$$ на $$$b_i$$$, т.е. присвоить $$$a_i := a_i + b_i$$$.
  • Вычесть: Уменьшить $$$a_i$$$ на $$$b_i$$$, т.е. присвоить $$$a_i := a_i - b_i$$$.

После завершения $$$k$$$-го хода итоговый счет вычисляется как максимальная сумма непустого подмассива измененного массива $$$a$$$. Цель Алисы — максимизировать итоговый счет, в то время как цель Боба — минимизировать итоговый счет.

Предполагая, что оба игрока играют оптимально для достижения своих целей, определите итоговый счет.

Максимальная сумма непустого подмассива массива $$$a$$$ определяется как $$$\max_{1 \leq i \leq j \leq n} S(i, j)$$$, где $$$S(i, j) = a_i + a_{i+1} + \cdots + a_j$$$. Обратите внимание, что пустые подмассивы не учитываются.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le 2\cdot 10^5$$$) — длина массивов и общее количество ходов.

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

Третья строка содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_{n}$$$ ($$$0 \le b_i \le 10^9$$$) — элементы массива $$$b$$$.

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

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

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

Пример
Входные данные
5
5 200000
3 -1 9 -5 4
0 0 0 0 0
4 5
10 10 10 10
1 1 1 1
3 1
2 -7 3
1 11 3
3 2
2 -7 3
1 11 3
1 1
-3
2
Выходные данные
11
41
9
3
-1
Примечание

Для первого набора входных данных:

  • Никакой ход не может изменить массив $$$a$$$, потому что все элементы в $$$b$$$ равны нулю.
  • Максимальная сумма непустого подмассива этого конечного массива равна $$$3 + (-1) + 9 = 11$$$.

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

  • Алиса добавляет $$$b_3=1$$$ к $$$a_3$$$. Массив $$$a$$$ становится $$$[10, 10, 11, 10]$$$.
  • Боб вычитает $$$b_1=1$$$ из $$$a_1$$$. Массив $$$a$$$ становится $$$[9, 10, 11, 10]$$$.
  • Алиса добавляет $$$b_3=1$$$ к $$$a_3$$$. Массив $$$a$$$ становится $$$[9, 10, 12, 10]$$$.
  • Боб вычитает $$$b_1=1$$$ из $$$a_1$$$. Массив $$$a$$$ становится $$$[8, 10, 12, 10]$$$.
  • Алиса добавляет $$$b_4=1$$$ к $$$a_4$$$. Массив $$$a$$$ становится $$$[8, 10, 12, 11]$$$.
  • Максимальная сумма непустого подмассива этого конечного массива равна $$$8+10+12+11 = 41$$$.

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

  • Алиса добавляет $$$b_2=11$$$ к $$$a_2$$$. Массив $$$a$$$ становится $$$[2, 4, 3]$$$.
  • Максимальная сумма непустого подмассива этого конечного массива равна $$$2 + 4 + 3 = 9$$$.

Для четвертого набора входных данных одна из возможных оптимальных последовательностей ходов:

  • Алиса добавляет $$$b_2=11$$$ к $$$a_2$$$. Массив $$$a$$$ становится $$$[2, 4, 3]$$$.
  • Боб вычитает $$$b_2=11$$$ из $$$a_2$$$. Массив $$$a$$$ становится $$$[2, -7, 3]$$$.
  • Максимальная сумма непустого подмассива этого конечного массива равна $$$3$$$.