B. Ферма пилюль Найфа
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

У заготовок есть рейтинги абсурдности $$$a_1, a_2, \ldots, a_n$$$, которые могут быть отрицательными. Мистер Найф должен опубликовать ровно $$$m$$$ заготовок в их исходном порядке. Их рейтинги образуют подпоследовательность$$$^{\text{∗}}$$$ $$$b$$$ массива $$$a$$$ длины $$$m$$$.

Его счёт пилюль изначально равен $$$0$$$. Когда он публикует $$$i$$$-ю выбранную заготовку, бот изменяет его счёт на $$$i \cdot (b_i - b_{i-1})$$$, где $$$b_0 = 0$$$. Отрицательное изменение уменьшает счёт, и счёт может становиться отрицательным. Таким образом, итоговый счёт пилюль равен $$$$$$ \sum_{i = 1}^{m} i \cdot (b_i - b_{i - 1}). $$$$$$

Какой максимальный счёт пилюль может получить мистер Найф, выбирая заготовки для публикации?

$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — количество заготовок и количество постов, которые должен опубликовать мистер Найф.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^7 \le a_i \le 10^7$$$) — рейтинги абсурдности заготовок.

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

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

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

Пример
Входные данные
6
5 3
0 8 1 7 3
4 3
0 -4 10 -2
4 2
0 5 -2 4
6 3
0 9 8 7 6 5
1 1
7
3 2
5 -100 4
Выходные данные
20
34
10
15
7
108
Примечание

В первом наборе входных данных мистер Найф может опубликовать заготовки с рейтингами $$$[0, 1, 7]$$$. Его итоговый счёт пилюль равен $$$$$$ 1 \cdot (0 - 0) + 2 \cdot (1 - 0) + 3 \cdot (7 - 1) = 20. $$$$$$

Во втором наборе входных данных он может опубликовать заготовки с рейтингами $$$[0, -4, 10]$$$. Второй пост уменьшает счёт, но третий пост с лихвой это компенсирует. Его итоговый счёт пилюль равен $$$$$$ 1 \cdot (0 - 0) + 2 \cdot (-4 - 0) + 3 \cdot (10 - (-4)) = 34. $$$$$$