C. Игра с массивом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых положительных чисел. За одну операцию вы должны выбрать некоторую пару $$$(i, j)$$$ такую, что $$$1\leq i < j\leq |a|$$$ и добавить $$$|a_i - a_j|$$$ к концу $$$a$$$ (то есть увеличить $$$n$$$ на $$$1$$$ и сделать новый элемент $$$a_n$$$ равным $$$|a_i - a_j|$$$). Ваша задача — минимизировать и вывести минимальный элемент $$$a$$$ после выполнения $$$k$$$ операций.

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

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

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

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

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

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

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

Пример
Входные данные
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000
Выходные данные
1
0
3
500000000000000000
Примечание

В первом наборе входных данных после любых $$$k=2$$$ операций минимальное значение $$$a$$$ будет равно $$$1$$$.

Во втором наборе входных данных оптимальная стратегия состоит в том, чтобы сначала выбрать $$$i=1, j=2$$$ и добавить $$$|a_1 - a_2| = 3$$$ к концу $$$a$$$, получив $$$a=[7, 4, 15, 12, 3]$$$. Затем выбрать $$$i=3, j=4$$$ и добавить $$$|a_3 - a_4| = 3$$$ к концу $$$a$$$, получив $$$a=[7, 4, 15, 12, 3, 3]$$$. В последней операции выбрать $$$i=5, j=6$$$ и добавить $$$|a_5 - a_6| = 0$$$ в конец $$$a$$$. Тогда минимальный элемент $$$a$$$ станет равным $$$0$$$.

В третьем наборе входных данных оптимальная стратегия состоит в том, чтобы сначала выбрать $$$i=2, j=3$$$ и добавить $$$|a_2 - a_3| = 3$$$ к концу $$$a$$$. Любая вторая операция все равно не приведет к тому, чтобы минимальное значение $$$a$$$ стало меньше $$$3$$$.