H. Деликатные анти-монотонные операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
I shall be looking for you who would be out of Existence.
— HyuN, Disorder

В жизни всегда много повторяющихся задач. Ирис они всегда не нравились, поэтому она отказывается их повторять. Однако время нельзя повернуть вспять; нам нужно только двигаться вперед.

Формально, у Ирис есть целочисленная последовательность $$$a_1, a_2, \ldots, a_n$$$, где каждое число в последовательности находится между $$$1$$$ и $$$w$$$ включительно. Гарантируется, что $$$w \geq 2$$$.

Ирис определяет операцию как выбор двух чисел $$$a_i, a_{i+1}$$$, удовлетворяющих $$$a_i = a_{i+1}$$$, а затем изменение их на два произвольных целых числа в пределах диапазона $$$[1, w]$$$. Ирис не нравится равенство, поэтому она должна гарантировать $$$a_i \neq a_{i+1}$$$ после операции. Каждая пара $$$a_i, a_{i+1}$$$ может быть выбрана несколько раз.

Ирис хочет узнать максимально возможную сумму всех элементов $$$a$$$ после нескольких (возможно, нуля) операций, а также минимальное количество операций, необходимое для достижения этого максимального значения.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq w$$$) — элементы массива.

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

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

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

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

В первом наборе входных данных никаких операций не может быть выполнено, поэтому ответами являются $$$\sum a_i = 15$$$ и $$$0$$$, соответственно.

Во втором наборе входных данных операции могут быть выполнены следующим образом:

$$$$$$[3, 1, 2, 3, 4, \underline{1, 1}] \rightarrow [3, 1, 2, 3, \underline{4, 4}, 5] \rightarrow [3, 1, 2, \underline{3, 3}, 5, 5] \rightarrow [3, 1, \underline{2, 2}, 5, 5, 5] \rightarrow [3, \underline{1, 1}, 5, 5, 5, 5] \rightarrow [\underline{3, 3}, 5, 5, 5, 5, 5] \rightarrow [4, 5, 5, 5, 5, 5, 5]$$$$$$

Можно показать, что это оптимально, поэтому мы должны вывести $$$\sum a_i = 34$$$ и количество операций $$$6$$$, соответственно.