문제2619--춸씅 패턴 인식 하기

2619: 춸씅 패턴 인식 하기

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 63  통과: 12
[제출] [채점기록] [묻고답하기]

문제 설명

이번 SHAKE 본선 C번 문제를 풀었다고 ? 하지만 지금은 못 풀걸 ? 이 대사는 쭈ㅖ리쒄뿌ㅖ가 콬캠오신 여러분에게 하는 말씀 이시다. 본선에서 못 푼 사람들을 모두 풀게 만들게 하시려는 쭈ㅖ리쒄뿌ㅖ는 문제를 간단화 시키셨다. 술을 3일 연속 마실수 없으며, 방학에는 시험을 보지 않기 때문에, 본선 처럼 시험 전날은 신경 안써도 된다. 하지만, 마지막 날은 반드시 술을 마셔야 한다. 안시의 박태환인 춸씅은 잠수 타는 패턴이 있다. 술을 마시면서 얻는 만족도가 최대가 되는 날 잠수를 타게 되는데, 이에 화가나는 안시 부회장은 춸씅의 잠수 타는 날을 찾아서, 잠수를 못타게 하려고 한다. 이런 안시 부회장을 돕기 위해, 춸씅이가 얻을 수 있는 최대 만족도를 구하시오.

(단, 2일 이상 굶을 수 없음).

입력 설명

test case $t$ $(1 \leq t \leq 2500)$가 들어오고 술을 마실수 있는 날($N$)의 수가 들어온다. $(1 \leq N \leq 300)$ 또한, enjoy($i$) : $i$번째 날 술을 마셨을때 얻을 수 있는 춸씅의 만족도가 $N$개 만큼 들어온다. (단, $1 \leq $enjoy($i$) $\leq 10^{4}$)

출력 설명

춸씅이 얻을 수 있는 최대 만족도를 출력하라.

입력 예시 Copy

1
6
10
20
15
25
10
20

출력 예시 Copy

75