시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
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 ≤ 105). W kolejnym wierszu znajduje się n liczb całkowitych a1, a2, ..., an (1 ≤ ai ≤ 109), oddzielonych pojedynczą spacją, oznaczających elementy A.
Zakładamy, że suma n we wszystkich zestawach danych nie przekroczy 106.
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).
2 3 2 1 1 1 5 3 1 2 2 3 3
2 6