Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_22_01 - Od zera do Billa Gatesa

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,103]. Pierwsza linia każdego testu składa się z dwóch liczb naturalnych n ∈ [2;106] 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 ≤ 107.

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

Dodane przez:Piotr Kąkol
Data dodania:2015-04-25
Limit czasu wykonania programu:0.5s-3.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.