숫자 볼링

축제에서 인기 있는 게임으로 숫자 볼링(Bowling for Numbers) 이 있습니다. 볼링 핀 여러 개가 한 줄로 놓여 있고, 각 핀에는 숫자가 하나씩 적혀 있습니다. 이 숫자는 그 핀을 쓰러뜨렸을 때 얻는 점수입니다. 당신에게는 볼링 공 몇 개가 주어지며, 각 공은 연속해서 인접한 핀 여러 개를 한 번에 쓰러뜨릴 수 있을 만큼 넓습니다.

예를 들어 핀이 다음과 같이 놓여 있다고 합시다.

2 8 5 1 9 6 9 3 2

공 두 개가 주어지고 각 공이 인접한 핀 세 개를 쓰러뜨릴 수 있다면, 얻을 수 있는 최대 점수는 $39$ 입니다. 한 번은 $2 + 8 + 5 = 15$ 를, 다른 한 번은 $9 + 6 + 9 = 24$ 를 쓰러뜨립니다. 한 번 쓰러진 핀은 다시 쓰러뜨릴 수 없으므로, 두 번의 투구는 서로 겹칠 수 없습니다.

아직 서 있는 핀들 중에서 매번 가장 점수가 높은 자리를 고르는 탐욕적 방법은 최댓값에 가까운 값을 주기는 하지만 항상 최댓값을 주지는 못합니다. 여러분이 할 일은 진짜 최대 점수를 구하는 것입니다.

각 공은 원래 줄에서 정확히 연속한 $w$ 개의 핀으로 이루어진 구간 하나를 쓰러뜨리며, 어떤 두 공도 같은 핀을 덮을 수 없습니다. 주어진 공을 모두 사용할 필요는 없습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다.

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 10$) 가 주어집니다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $k$, $w$ 가 주어집니다.

• $n$ ($1 \le n \le 30000$) — 볼링 핀의 개수
• $k$ ($1 \le k \le 500$) — 사용할 수 있는 공의 개수
• $w$ ($1 \le w \le n$) — 각 공의 너비, 즉 한 번에 쓰러뜨리는 인접한 핀의 개수

이어지는 $n$ 개의 줄에는 각 핀의 점수가 순서대로 주어지며, 각 값은 $10000$ 미만의 음이 아닌 정수입니다.

각 테스트 케이스마다 플레이어가 얻을 수 있는 최대 점수를 한 줄에 출력합니다. 이 점수는 항상 10억 미만임이 보장됩니다.