E. Мексификация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$. Вы выполняете следующую процедуру $$$k$$$ раз:

  • Для каждого элемента $$$a_i$$$ он присваивает $$$a_i$$$ значение $$$\operatorname{mex}$$$$$$^{\text{∗}}$$$$$$(a_1,a_2,\ldots,a_{i-1},a_{i+1},a_{i+2}, \ldots,a_n)$$$. Другими словами, он присваивает $$$a_i$$$ значение $$$\operatorname{mex}$$$ всех остальных элементов массива. Это делается для всех элементов массива одновременно.

Пожалуйста, найдите сумму элементов в массиве после всех $$$k$$$ операций.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$d_1, d_2, \ldots, d_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$d$$$.

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

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 2\cdot 10^5, 1 \leq k \leq 10^9$$$) – количество элементов в $$$a$$$ и количество выполненных операций.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq n$$$).

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

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

Для каждого набора входных данных выведите сумму элементов после всех $$$k$$$ операций на новой строке.

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

В первом примере мы выполнили операцию над массивом $$$[0,2,1]$$$ три раза. Давайте вычислим результат после первого раза:

  • Первый элемент становится $$$\operatorname{MEX}(2,1)=0$$$
  • Второй элемент становится $$$\operatorname{MEX}(0,1)=2$$$
  • Третий элемент становится $$$\operatorname{MEX}(0,2)=1$$$

Таким образом, после первой операции $$$[0,2,1]$$$ снова становится $$$[0,2,1]$$$. Можно показать, что массив не изменится, независимо от того, сколько раз мы выполняем операцию, поэтому финальный массив после трех операций все еще $$$[0,2,1]$$$. Сумма равна $$$0+2+1=3$$$.

В третьем примере массив становится $$$[2,2,2,2]$$$.