Zmaksymalizowany podzbiór

Limit pamięci: 32 MB

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

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

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita (), 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 oraz (). W kolejnym wierszu znajduje się liczb całkowitych (), oddzielonych pojedynczą spacją, oznaczających elementy .

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

Dodatkowo, w testach wartych około punktów suma wszystkich nie przekroczy .

Wyjście

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

Przykład

Dla danych wejściowych:

2
3 2
1 1 1
5 3
1 2 2 3 3

poprawną odpowiedzią jest:

2
6

Autor zadania: Adrian Jaskółka (zapożyczenie).