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

Дан массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел, а также целочисленный параметр $$$k$$$.

Пока в массиве не менее $$$k$$$ элементов, необходимо выполнять одну из следующих операций двух типов над $$$a$$$:

  • Удалить $$$a_k$$$ и прибавить его значение к счёту или
  • удалить $$$a_{m-k+1}$$$ и прибавить его значение к счёту, где $$$m$$$ — длина $$$a$$$ до выполнения этой операции.

После удаления элемента оставшиеся элементы сохраняют свой относительный порядок.

Определите максимально возможный счёт, который можно получить.

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

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

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

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

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

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

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

Пример
Входные данные
4
4 2
1 2 3 4
4 4
3 4 1 2
1 1
1
6 3
1 4 8 2 6 3
Выходные данные
9
3
1
19
Примечание

В первом наборе входных данных сначала можно удалить $$$a_3 = 3$$$. Счёт становится равен $$$3$$$, а массив принимает вид $$$[1, 2, 4]$$$. Затем удалим $$$a_2 = 2$$$, после чего счёт станет равен $$$5$$$, а массив примет вид $$$[1, 4]$$$. Наконец, удалим $$$a_2 = 4$$$, и счёт станет равен $$$9$$$. Теперь длина массива меньше $$$k=2$$$, поэтому выполнить ещё одну операцию невозможно. Можно доказать, что максимальный счёт равен $$$9$$$.

Во втором наборе входных данных можно выполнить только одну операцию: удалить либо $$$a_1 = 3$$$, либо $$$a_4 = 2$$$. Очевидно, что лучше удалить $$$a_1 = 3$$$ и получить счёт $$$3$$$.