문제1232--깃발 꽂기!

1232: 깃발 꽂기!

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

종욱이는 영준이가 개발한 깃발 꽂기 게임을 하기로 하였습니다.

일렬로 늘어진 0을 포함한 양의 정수의 지도가 주어졌을때, 각 깃발은 하기의 특별한 규칙에 따라서 점수를 산정한다고 합니다.
 - 깃발을 꽂은 위치를 포함한 최대 연속된 R개 만큼의 영역이 깃발을 꽂은 위치의 점수로 바뀌게 됩니다.
 - 단, 인접한 위치에 꽂힌 서로 다른 깃발이 같은 영역을 차지할 수는 없습니다.

위의 규칙에 따라 종욱이가 깃발 꽂기를 진행할때, 과연 종욱이가 얻을 수 있는 최대 점수는 몇점일까요?

예시는 다음과 같습니다.
     - 예 1) R = 1 이고, 입력으로 1,2,3 이 주어졌을때의 최대 점수는 6 ([1], [2], [3]) 이 됩니다.
     - 예 2) R = 2 이고, 입력으로 1,2,3,4 가 주어졌을때의 최대 점수는 12 ([2,2], [4,4]) 가 됩니다.
     - 예 3) R = 3 이고, 입력으로 7,2,3,6,5,1,4,8 가 주어졌을때의 최대 점수는 57 ([7,7,7], [6,6], [8,8,8]) 이 됩니다.

입력 설명

처음 줄에는 
정수 T ( 1 <= T <= 1000 ) 가 주어지며, T는 총 테스트 케이스의 입력 수를 의미합니다.
그 다음 줄부터 총 T줄에 걸쳐 배열의 구성 요소 숫자를 의미하는 J ( 1 <= J <= 500 ) 그리고 깃발을 꽂았을때 최대로 확보할 수 있는 영역을 의미하는 R ( 1 <= R <= J ), 마지막으로 숫자 N ( 0 <= N <= 100 ) 이 J개 만큼 입력으로 주어집니다.

출력 설명

문제 설명에서 명시한 규칙에 따라서 얻을 수 있는 가장 높은 점수를 출력하세요.

입력 예시 Copy

3
3 1 1 2 3
4 2 1 2 3 4
8 3 7 2 3 6 5 1 4 8

출력 예시 Copy

6
12
57

출처/분류