숫자 볼링++

'숫자 볼링(Bowling for Numbers)'이라는 게임을 한다. 볼링 핀 $n$개가 한 줄로 서 있고, $i$번째 핀에는 정수 점수 $a_i$가 적혀 있다. 이는 그 핀을 쓰러뜨렸을 때 얻는 점수다. 일부 핀은 점수가 음수인 벌점 핀이라서, 쓰러뜨리면 오히려 총점이 깎인다.

당신에게는 볼링공 $k$개가 주어진다. 각 공은 연속한 핀을 최대 $w$개까지 쓰러뜨릴 만큼 넓다. 즉 한 번 던지면 인접한 $w$개 위치로 이루어진 구간을 덮고, 그 구간 안에 아직 서 있는 핀을 모두 쓰러뜨린다. 한 핀의 점수는 공이 몇 개 지나가든 최대 한 번만 계산된다.

던진 공의 구간은 줄의 왼쪽이나 오른쪽 끝을 넘어갈 수 있고(끝 바깥은 모두 빈 공간이다), 앞서 던진 공이 이미 쓰러뜨려 생긴 빈틈을 지나갈 수도 있다. 이를 이용할 수 있다. 구간의 $w$개 위치 중 일부가 빈 공간(줄의 바깥이거나 이전 투구로 이미 치워진 위치)에 놓이도록 겨냥하면, $w$개보다 적게 쓰러뜨리면서 벌점 핀을 피할 수 있다. 아무 핀도 쓰러뜨리지 않도록 공을 던져도 된다.

$k$개의 공을 던져 쓰러뜨린 핀들의 총점을 최대로 만들어라. 모든 공을 반드시 쓸 필요는 없다.

이는 다음과 동치다. 쓰러지는 핀은 당신이 던진 (최대 $k$개의) 길이 $w$짜리 구간 중 적어도 하나에 덮이는 위치의 핀이고, 점수는 덮인 모든 위치의 $a_i$의 합이다. 얻을 수 있는 최대 점수를 구하라.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$)가 주어진다. 이어서 각 테스트 케이스가 주어진다.

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

• $n$ ($1 \le n \le 10000$) — 핀의 개수
• $k$ ($1 \le k \le 500$) — 공의 개수
• $w$ ($1 \le w \le 100$) — 공의 너비, 즉 한 번 던져 쓰러뜨릴 수 있는 연속한 핀의 최대 개수

다음 $n$개의 줄에는 각각 정수가 하나씩 주어지며, 왼쪽부터 순서대로 각 핀의 점수를 나타낸다. 모든 점수는 $-10000 \le a_i \le 10000$을 만족한다.

각 테스트 케이스마다 얻을 수 있는 최대 총점을 한 줄에 출력한다. 답은 10억 미만임이 보장된다.