Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bowling là một trò chơi giải trí mà người chơi ném một quả bóng nặng cho chạy trên một đường băng dài và phẳng để làm đổ những chai gỗ đứng ở cuối đường. Ngày nay, Bowling được xem là một môn thể thao. Trong bài toán này chúng ta sẽ xét trò chơi Bowling cải biên như sau:

- Cuối đường băng người ta đặt n chai gỗ được xếp thành một hàng ngang, các chai gỗ được đánh số từ 1 đến n từ trái qua phải. Chai gỗ thứ i ghi số nguyên a_i tương ứng là điểm thưởng (nếu a_i≥0) hoặc phạt (nếu a_i<0) khi ném bóng mà làm đổ chai gỗ này.

- Người chơi phải ném ít nhất một lần và không giới hạn số lần ném bóng. Mỗi lần ném bóng, người chơi sẽ ném bóng hướng vào một trong n vị trí đặt chai gỗ, nếu ném bóng hướng vào vị trí đặt chai gỗ thứ i thì nó sẽ làm đổ những chai đặt ở vị trí có khoảng cách với vị trí chai thứ i không vượt quá r. Khoảng cách giữa vị trí hai chai thứ i và thứ j được tính là |i – j|. Tổng điểm mà người chơi đạt được là tổng các số ghi trên các chai gỗ mà người chơi làm đổ được. Muốn đạt được nhiều điểm người chơi không những phải có khả năng thực hiện việc ném bóng chính xác mà còn phải biết lựa chọn hướng ném bóng trong mỗi lượt chơi. 

Yêu cầu: Cho r và a₁, a₂, …, a_n, hãy tính tổng điểm lớn nhất mà người chơi có thể đạt được với giả thiết người chơi có khả năng thực hiện chính xác việc ném bóng.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên ghi số nguyên dương K (K≤10) là số lượng bộ dữ liệu. Tiếp đến là  K nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:

• Dòng thứ nhất ghi hai số nguyên dương n và r (r ≤ n ≤ 200000);
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n, số a_i tương ứng là số ghi trên chai gỗ thứ i (|a_i|≤10⁹).

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng một số nguyên là tổng điểm mà người chơi có thể đạt được tương ứng với bộ dữ liệu trong dữ liệu vào.

Example

Input:
2
5 1
1 0 -10 0 1
5 1
-1 -1 -1 -1 -1

Output:
2
-2