AlgoLiga 2018

Już od przedszkola największym idolem Przemka był Bill Gates. Wyobrażał on sobie ile Knoppersów mógłby kupić gdyby był tak bogaty, jak właściciel kodeksu Leicester. Imał się różnych prac, grał w pokera i na giełdzie, nie ogranicza się w sposobach na zdobycie pieniędzy. Zobaczył ostatnio promocję w Old Yorkerze "k w cenie k-1". Przy kupnie każdych k rzeczy za najtańszą się nie płaci.  Przemek wpadł na pomysł, że nakupuje trochę ubrań w promocji, a następnie sprzeda je na Adagio. Ważne jest jednak by jak najwięcej zaoszczędzić na kupnie rzeczy, by zysk był jak największy. Jeżeli kupi wszystko na raz to zaoszczędzi jedynie na kilku najtańszych ciuchach. A może gdybym podzielił zakupy na kilka części, to zyskałbym więcej? Pomóż Przemkowi ustalić ile maksymalnie może zaoszczędzić na kupnie n ciuchów jeśli za każde k kupionych najtańsze dostanie gratis. Być może gdy Przemek w końcu zdobędzie fortunę, to podzieli się z Tobą Knoppersami.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t ∈ [1,10³]. Pierwsza linia każdego testu składa się z dwóch liczb naturalnych n ∈ [2;10⁶] i k ∈ [2;n]. Druga linia zawiera z kolei n liczb naturalnych będących cenami ubrań, które kupił Przemek. Żadna cena nie przekracza 8590 zł. Dodatkowo, t*n ≤ 10⁷.

Wyjście

Dla każdego testu należy wypisać jedną liczbę - maksymalną kwotę jaką Przemek może zaoszczędzić na kupnie ciuchów.

Przykład

Wejście:
1
7 4
60 70 30 80 20 90 40

Wyjście:
60