406799: GYM102558 F Поиск

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

Разработчики Яндекс.Поиска постоянно работают над улучшением алгоритмов ранжирования. Один из алгоритмов, который хотят опробовать, таков.

Поисковый алгоритм состоит из трёх этапов: поиск по базе, отбор документов и фильтрация. Во время поиска по базе отбираются $$$n$$$ документов-кандидатов для показа пользователю. Каждому документу сопоставляется целое число — релевантность, показывающее, насколько документ подходит пользователю. Чем выше релевантность, тем лучше документ подходит по данному запросу. Обратите внимание, что релевантность может быть даже отрицательной в случае, если документ не имеет никакого отношения к запросу.

Ранжирующий алгоритм хранит данные в закольцованном списке, таким образом, после документа с номером $$$i$$$ ($$$i < n$$$) следующим в списке является документ с номером $$$i + 1$$$, а следующим после документа с номером $$$n$$$ будет документ с номером $$$1$$$. Во время отбора документов алгоритм выберет некоторый документ (назовём его начальным) и сколько-то следующих за начальным документов, которые будут переданы на фильтрацию.

Во время фильтрации из списка документов, полученных при отборе, может быть удалено несколько документов, но не более $$$k$$$. Кроме того, после фильтрации должен остаться хотя бы один документ. Оставшиеся после фильтрации документы показываются пользователю.

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

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

В первой строке задано целое число $$$t$$$ — количество тестовых случаев. Далее следует описание тестовых случаев.

Описание каждого теста состоит из двух строк.

В первой строке задано два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 100\,000$$$, $$$0 \leq k \leq min(n - 1, 100)$$$) — количество документов, полученных во время поиска, и максимальное количество документов, которые могут быть удалены после фильтрации соответственно.

Во второй строке содержатся $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — релевантности документов.

Гарантируется что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$100\,000$$$.

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

Для каждого тестового случая выведите одно целое число — ответ на задачу.

ПримерВходные данные

6
4 0
1 -2 9 10
6 1
5 -5 5 -5 5 -5
6 2
5 -5 5 -5 5 -5
4 3
5 -5 5 -5
8 1
-3 -1 5 6 -200 -200 5 -1
3 1
-1 -2 -3

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

20
10
15
10
14
-1

Примечание

В первом примере выгодно выбрать в качестве начального документ с релевантностью $$$9$$$ и отправить на фильтрацию его и следующие 2 документа. На стадии фильтрации необходимо оставить все документы.

Во втором примере выгодно выбрать в качестве начального любой документ с релевантностью $$$5$$$, отправить на стадию фильтрации его и следующие за ним 2 документа. На стадии фильтрации необходимо удалить документ с релевантностью $$$-5$$$, таким образом, на выдачу попадут два документа с релевантностью $$$5$$$.

В пятом примере выгодно выбрать в качестве начального документ с номером $$$7$$$ и отправить на стадию фильтрации его и следующие $$$5$$$ документов. Таким образом, на стадию фильтрации попадут документы с релевантностями $$$[5, -1, -3, -1, 5, 6]$$$. На стадии фильтрации выгодно удалить документ с релевантностью $$$-3$$$, в результате чего на выдачу попадут документы с релевантностями $$$[5, -1, -1, 5, 6]$$$ с суммарной релевантностью $$$14$$$.

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