Restauracja Calabria, która częstowała pizzą uczestników III Warmińsko-Mazurskich zawodów
w programowaniu, jest wyposażona w automatyczny piec do wypiekania ciast. Piec ma na wejściu
taśmę z ułożonymi ciastami (każde ciasto ma swój czas wypiekania). Piec mieści naraz M sztuk ciast.
Twoim zadaniem jest tak podzielić ciasta na kolejne wkłady do pieca aby zminimalizować czas
wypiekania. Kolejny wkład można umieścić w piecu tylko jak skończą się wypiekać wszystkie ciasta
z poprzedniego. Nie możemy zmieniać kolejności ciast na taśmie, możemy za to dowolnie dzielić
ciasta na kolejne wkłady (maksymalnie M kolejnych ciast). Trzeba obliczyć i wyświetlić najkrótszy
możliwy czas wypiekania.

Przykładowo, piec mieści dwa ciasta (M=2). Na taśmie mamy kolejne czasy wypiekania:
2 10 10. Najkrótszy całkowity czas będzie wynosił 12. Pierwszy wkład ─ pierwsze ciasto, drugi wkład ─
równocześnie ciasto drugie i trzecie. Gdybyśmy podzielili ciasta inaczej, to czas wypiekania byłby 20.

Wejście

Wejście zaczyna się od liczby całkowitej N (N<23) określającej liczbę przypadków. Każdy
przypadek składa się z dwóch linii. W pierwszej linii znajduje się liczba M (liczba ciast mieszczących się
w piecu) oraz liczba K, długość taśmy (K<1001). W drugiej linii jest M liczb naturalnych, oznaczających
czasy wypiekania poszczególnych ciast na taśmie. Każdy czas wypiekania nie przekracza 100.

Wyjście

Dla każdego przypadku należy obliczyć i wyświetlić w jednej linii liczbę całkowitą, najkrótszy
możliwy czas wypiekania podanej kolejki.

Przykładowe dane

Weiście:
2
2 3
2 10 10
2 3
7 5 2

Wyjście:
12
9