Từ lâu, tại vương quốc Brainrot, người ta truyền tai nhau về một dòng dõi thuần tinh tinh – dòng họ Chimpanzee. Theo sử sách, tổ tiên của Chimpanzee đã từng giúp thần Nông bội thu muôn vườn, khiến đất đai trù phú, dân chúng ấm no.

Chimpanzinni Bananinni, chú tinh tinh đời thứ ~97~ trong dòng tộc, sinh ra dưới ánh trăng bạch kim trên đỉnh núi Siêu Chuối. Ngay từ nhỏ, Chimpanzinni Bananinni đã thể hiện năng khiếu bắt sóng năng lượng cây trồng: chỉ cần chạm nhẹ là cánh đồng liền tỏa sáng rực rỡ. Khi lớn lên, Chimpanzinni Bananinni rời núi, lang thang khắp nơi để tìm kiếm thử thách mới.

Một ngày nọ, Chimpanzinni Bananinni đến Trại Chuối Ngự – nơi sở hữu hàng ~n~ cây chuối chứa tinh hoa thần nông, mỗi cây thứ ~i~ ẩn chứa ~a_i~ quả chuối ngự tinh túy. Trại do phù thủy Tung Tung Tung Sahur cai quản, người đã đặt ra bài toán không đơn giản:

• Muốn khai thác tinh hoa, người hái phải tuân theo Lời Nguyền Chu Kỳ:
  • Chỉ được phép hái chuối tối đa ở ~k~ cây liên tiếp.
  • Sau đó phải bỏ qua (không hái) ít nhất ~k~ cây tiếp theo để đất đai hồi sinh, nếu không linh hồn của Tralalero Tralala sẽ trỗi dậy và trừng phạt.

Yêu cầu: Hiện nay Chimpanzinni Bananinni cần một chiến lược thông minh để thỏa mãn Lời Nguyền Chu Kỳ mà vẫn thu thập được nhiều quả chuối ngự nhất. Bạn hãy đồng hành cùng Chimpanzinni Bananinni để tìm ra chiến lược đó.

Input

• Dòng đầu: số testcase ~T~ ~(T \leq 10)~.
  • Mỗi testcase gồm:
    • Dòng ~1~: Chứa hai số nguyên ~n, k~ lần lượt là số lượng cây chuối và giới hạn hái - bỏ qua ~(k \leq n \leq 10^6)~
    • Dòng ~2~: Gồm ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ lầ lượt là số lượng quả chuối ở cây thứ ~i~ ~(a_i \leq 10^9)~.

Output

• Gồm ~T~ dòng, mỗi dòng là số quả chuối ngự tối đa Chimpanzinni Bananinni thu được ở testcase tương ứng.

Sample Input

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

Sample Output

4
22

Notes

• Ở testcase thứ ~2~:
  • Chimpanzinni Bananinni hái ở cây ~3–4~ ~(5 + 5 = 10~ quả~)~
  • Nghỉ không hái ở cây ~5–7~
  • Tiếp tục hái ở cây ~8–9~ ~(3 + 9 = 12~ quả~)~
  • Tổng cộng: ~10 + 12 = 22~ quả chuối ngự.