406799: GYM102558 F Поиск

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

Поисковый алгоритм состоит из трёх этапов: поиск по базе, отбор документов и фильтрация. Во время поиска по базе отбираются $$$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$$$.

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