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

Задан массив целых чисел $$$a$$$ размером $$$n$$$. Изначально все элементы массива окрашены в красный цвет.

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

Стоимость покраски массива определяется как сумма первых $$$k$$$ выбранных элементов и последнего окрашенного элемента.

Ваша задача — посчитать максимальную возможную стоимость покраски для заданного массива.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 5000$$$; $$$1 \le k \lt n$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

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

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

Пример
Входные данные
3
3 1
1 2 3
5 2
4 2 3 1 3
4 3
2 2 2 2
Выходные данные
5
10
8
Примечание

В первом примере изначально вы можете покрасить $$$2$$$-й элемент, а затем красить элементы в порядке $$$1, 3$$$. Тогда стоимость покраски равна $$$2+3=5$$$.

Во втором примере изначально вы можете покрасить элементы $$$1$$$ и $$$5$$$, а затем красить элементы в порядке $$$2, 4, 3$$$. Тогда стоимость покраски равна $$$4+3+3=10$$$.

В третьем примере изначально вы можете покрасить элементы $$$2, 3, 4$$$, а затем покрасить $$$1$$$-й элемент. Тогда стоимость покраски равна $$$2+2+2+2=8$$$.