Trong một trò chơi tại một lễ hội, người chơi đối mặt với một dãy các bowling pins được sắp xếp thành hàng. Mỗi pin có in một con số, thể hiện điểm số có được khi làm đổ pin đó. Người chơi được cung cấp một số bóng bowling; mỗi bóng đủ rộng để có thể làm đổ một vài pin liên tiếp liền kề.

Ví dụ, dãy các pin có điểm số như sau:

5 8 7 10 6 9 4 3

Nếu người chơi có hai quả bóng, mỗi quả có thể làm đổ ba pin liền kề, điểm số tối đa mà người chơi có thể đạt được là 45, với hai lượt ném như sau: 5+8+7 = 20 và 10+6+9 = 25.

Để tăng độ khó, trò chơi đã thêm vào khái niệm pin phạt. Pin phạt là các pin có điểm âm, làm giảm điểm số của người chơi khi làm đổ chúng. Điều này yêu cầu người chơi phải thay đổi chiến lược để tránh ném vào các pin phạt.

Xét ví dụ sau:

1 9 -4 2 5 7 5 9 -4

Nếu người chơi có ba quả bóng, mỗi quả có thể làm đổ ba pin liền kề, điểm số tối đa người chơi có thể đạt được là 38, với ba lượt ném như sau: 1+9, 2+5+7, và 5+9. Người chơi ném quả đầu tiên vào 1+9, tránh pin phạt -4; quả thứ hai vào 2+5+7, và quả thứ ba vào 5+9, tránh pin phạt -4.

Một chiến lược khác là mỗi lượt chọn cú ném có điểm số cao nhất từ các pin còn lại. Chiến lược này không luôn đạt điểm tối đa, nhưng có thể đạt điểm gần với tối đa.

Input

Dữ liệu đầu vào gồm nhiều bộ test. 

Dòng đầu tiên là số nguyên t, 1 ≤ t ≤ 10, là số bộ test.

Với mỗi bộ test:

Dòng đầu chứa ba số nguyên:

• n, 1 ≤ n ≤ 10007, số lượng pin.
• k, 1 ≤ k ≤ 510, số lượng bóng bowling.
• w, 1 ≤ w ≤ 110, độ rộng của bóng bowling (số pin liền kề mà bóng có thể làm đổ).

n dòng tiếp theo, mỗi dòng là một số nguyên thể hiện điểm số của một pin, theo thứ tự.

Output

Với mỗi bộ test, xuất ra điểm số tối đa mà người chơi có thể đạt được. Điểm số này đảm bảo nhỏ hơn một tỷ.