Carota đi làm ở công ty chuyên trồng carrot trong n giờ. Cách trả tiền lương cho công ty này rất kỳ lạ, nếu Carota làm việc ở giờ thứ ~i~ thì anh được ~a_i~ dollars.

Carota có thể làm liên tiếp trong tối đa ~k~ giờ (có thể làm ít hơn) và sau đó phải nghỉ trong ít nhất ~k~ giờ tiếp theo. Biết Carota có thể chọn thời gian làm việc tùy ý, hãy tính số tiền lớn nhất mà Carota có thể kiếm được.

Input

• Dòng ~1~: Một số nguyên dương ~T~ - số test ~(T \leq 5)~
• Các dòng tiếp theo mô tả ~T~ bộ test, mỗi test có định dạng như sau:
  • Dòng ~1~: Hai số nguyên dương ~n~, ~k~ tương ứng là số giờ và thời gian làm tối đa cũng như nghỉ ít nhất của Carota.
  • Dòng ~2~: Gồm ~n~ số nguyên không âm, số thứ ~i~ là ~a_i~.

Output

• Gồm ~T~ dòng, dòng thứ ~i~ là số tiền lớn nhất mà Carota có thể kiểm được trong test thứ ~i~.

Example Input

2
7 2
1 1 0 0 0 1 1
9 3
0 0 5 5 0 5 2 3 9

Example Output

4
22

Giải thích

• Trong test thứ ~2~, Carota làm việc từ giờ thứ ~3~ đến giờ thứ ~4~, sau đó nghỉ ~3~ tiếng rồi lại làm tiếp từ giờ thứ ~8~ đến giờ thứ ~9~.

Giới hạn

• ~k \leq n~ với mọi test
• ~35\%~ số test có ~n \leq 10^2~
• ~30\%~ số test có ~n \leq 10^3~
• ~15\%~ số test có ~n \leq 10^5~
• ~20\%~ số test có ~T = 1~ và ~n = 10^6~