EIU Programming Practices and Exams

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]$.

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: T - số test (T <= 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
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 <= n với mọi test
• 35% số test có n <= 10²
• 30% số test có n <= 10³
• 15% số test có n <= 10⁵
• 20% số test có T = 1 và n = 10⁶