#2619 춸씅 패턴 인식 하기

1 s   128 MB  

Description

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

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

Input

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}$)

Output

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

Sample Input

Sample Output

1
6
10
20
15
25
10
20
75

Source

2015 ANSI Summer Coding Camp / BOJ 2579 / KOI 2006 초등부 4번 / data set by wowoto9772(최승주)