Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUDP2 - Carota đi làm

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 <= 102
  • 30% số test có n <= 103
  • 15% số test có n <= 105
  • 20% số test có T = 1 và n = 106

Added by:Ha Minh Ngoc
Date:2016-05-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:hgminh95
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.