İqtisadiyyat
Təsəvvür edin ki, siz ACM ICPC dünya finalını yeni qazanmış komandanın kapitanısınız və indi bu qələbəni sizinlə birlikdə olan k-1 dostunuzla qeyd etməlisiniz. Bunun üçün yaxın mağazadan sevimli içkinizin n butulkasını almaq lazımdır (hansı içki olduğunu yalnız təxmin edə bilərsiniz). i-ci butulkanın qiyməti c_i rubl təşkil edir. Təəssüf ki, satıcı çoxlu butulka alan müştəriləri sevmir, buna görə də daha əvvəl ondan alış-veriş etmiş müştəri üçün butulkanın qiymətini dəyişir. Dəqiq desək, əgər müştəri artıq x butulka alıbsa, i nömrəli butulkanı almaq üçün (x+1)·c_i rubl ödəməlidir.
n butulkanı almaq üçün minimal mümkün xərci müəyyən etmək lazımdır, nəzərə alaraq ki, alış prosesində ən çox k nəfər iştirak edə bilər (yalnız siz və dostlarınız).
Giriş verilənləri
Birinci sətir testlərin sayını t (t ≤ 100) ehtiva edir. Hər bir test iki sətirdən ibarətdir. Birinci sətir iki tam ədəd n və k (1 ≤ n, k ≤ 100) ehtiva edir. İkinci sətir n müsbət tam ədədlər c_1, c_2, ..., c_n - alışların müvafiq qiymətlərini ehtiva edir (1 ≤ c_i ≤ 10^6).
Çıxış verilənləri
Hər bir test üçün ayrıca sətirdə optimal alış xərci göstərin.