== include(page="template/taskheader" task_id="peru") ==

Sunt $N$ gandaci in linie (atentie, nu cerc). Gandacul i are o carapace de rezistenta R[i].
Ai o manusa pe care o poti folosi pentru a lovi $K$ gandaci consecutivi deodata, la orice pozitie vrei, de cate ori vrei.
Atunci cand depui efortul $E$, toti gandacii cu rezistenta mai mica de $E$ sunt striviti, iar ceilalti nu patesc NIMIC. Efortul poate fi diferit de la o lovitura la alta. Se dau $T$ astfel de scenarii. Pentru fiecare scenariu, care e efortul total minim pentru a strivi toti gandacii?

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $peru.in$ contine pe prima linie $T$, numarul de gandaci.
Urmatoarele $2 * T$ linii contin descrierea testelor, cate doua linii pentru fiecare test:
Prima linie contine $N$ si $K$, iar a doua linie contine vectorul $R$ de lungime $N$.

Fişierul de intrare $peru.in$ ...

h2. Date de ieşire

În fişierul de ieşire $peru.out$ contine $T$ linii, pe linia $i$ aflandu-se raspunsul pentru al $i$-lea test.

În fişierul de ieşire $peru.out$ ...

h2. Restricţii

* $1 ≤ T, suma N-urilor, K ≤ 10^6^$
* Pentru $20%$ din punctaj $1 ≤ suma N-urilor ≤ 5000$
* Pentru $40%$ din punctaj $1 ≤ suma N-urilor ≤ 10^5^$
 
O(N) 100p
O(Nlog) 60p
O(NK) 20p
 

* $... ≤ ... ≤ ...$

h2. Exemplu