198. Поиск

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

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

Ранжирующий алгоритм хранит данные в закольцованном списке, таким образом после документа с номером $i$ ($i \lt 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$.

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

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

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

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

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