Дан массив $$$A$$$ из $$$N$$$ целых чисел. Требуется выбрать $$$K$$$ непустых подпоследовательностей (символы необязательно подряд идущие). Счёт подпоследовательности равен её $$$\rm{mex}$$$ (mex — это минимальное неотрицательное целое число, не встречающееся в последовательности).
Выберите любые $$$K$$$ различных непустых подпоследовательностей и разместите их счёты в любом порядке, после чего добавьте счёты с нечётными индексами к $$$y$$$ и вычтите счёты с чётными индексами из $$$y$$$ (изначально $$$y=0$$$). Более формально: Пусть $$$S$$$ — последовательность счётов, тогда $$$y=S_1-S_2+S_3-\dots-(-1)^K S_K$$$.
Найдите минимальное возможное значение $$$y$$$.
Две подпоследовательности различны в том случае, если существует такой индекс $$$i$$$, что в одной из подпоследовательностей $$$i$$$-й элемент присутствует, а в другой нет. (Таким образом существует $$$2^N-1$$$ непустых подпоследовательностей.)
Первая строка входных данных содержит целое число $$$T$$$ ($$$1 \le T \le 100000$$$) - количество наборов входных данных
Каждый набор состоит из 2 строк:
Первая строка содержит два целых числа $$$N$$$ ($$$1 \le N \le 100000$$$) и $$$K$$$($$$1 \le K \le \min(10^9,2^N - 1)$$$ — размер массива и количество подпоследовательностей, которых нужно выбрать.
Вторая строка содержит $$$N$$$ целых чисел массива $$$A$$$. Для каждого $$$i$$$, $$$0 \le A_i \le 10^9$$$.
Гарантируется, что сумма $$$N$$$ по наборам входных данных не превышает $$$100000$$$.
Для каждого набора входных данных нужно вывести одно целое число — минимальное возможное значение $$$y$$$, которое можно получить.
36 40 0 2 3 1 48 71 2 3 0 1 2 4 63 11 5 2
-10 -15 0
| TheForces Round #26 (Readall-Forces) |
|---|
| Закончено |
