8709번 - Zmaksymalizowany podzbiór 다국어

문제

Niech f(A) będzie funkcją, która dla podanego multizbioru A (czyli zbioru, w którym elementy mogą się powtarzać) zwraca taką liczbę x, że każdą z liczb od 1 do x można przedstawić jako sumę elementów pewnego podzbioru A (w tym zadaniu zakładamy, że podzbiór multizbioru też jest multizbiorem), natomiast liczby x + 1 już jako sumy elementów pewnego podzbioru A przedstawić się nie da.

Mając podany pewien n-elementowy multizbiór A, Twoim zadaniem jest znalezienie k-elementowego podzbioru B, takiego że wartość f(B) jest największa z możliwych.

입력

W pierwszej linii wejścia znajduje się jedna liczba całkowita t (1 ≤ t ≤ 100), oznaczająca liczbę zestawów danych. Opis każdego zestawu danych składa sie z dwóch wierszy. W pierwszej linii każdego zestawu danych znajdują się dwie liczby całkowite n oraz k (1 ≤ k ≤ n ≤ 10⁵). W kolejnym wierszu znajduje się n liczb całkowitych a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹), oddzielonych pojedynczą spacją, oznaczających elementy A.

Zakładamy, że suma n we wszystkich zestawach danych nie przekroczy 10⁶.

출력

Na wyjściu dla każdego zestawu danych powinna znaleźć się w oddzielnej linii jedna liczba całkowita, oznaczająca maksymalną możliwą wartość f(B).

제한

힌트