You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ positive integers. 

Initially you are standing at index $1$ and have a score equal to $a_1$. You can perform two kinds of moves:   move right — go from your current index $x$ to $x+1$ and add $a_{x+1}$ to your score. This move can only be performed if $x<n$.  move left — go from your current index $x$ to $x-1$ and add $a_{x-1}$ to your score. This move can only be performed if $x>1$. Also, you can't perform two or more moves to the left in a row. 

You want to perform exactly $k$ moves. Also, there should be no more than $z$ moves to the left among them.

What is the maximum score you can achieve?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains three integers $n, k$ and $z$ ($2 \le n \le 10^5$, $1 \le k \le n - 1$, $0 \le z \le min(5, k)$) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$) — the given array.

The sum of $n$ over all testcases does not exceed $3 \cdot 10^5$.


-----Output-----

Print $t$ integers — for each testcase output the maximum score you can achieve if you make exactly $k$ moves in total, no more than $z$ of them are to the left and there are no two or more moves to the left in a row.


-----Example-----
Input
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9

Output
15
19
150
56



-----Note-----

In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score $a_1 + a_2 + a_3 + a_4 + a_5$.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be $a_1 + a_2 + a_3 + a_2 + a_3$.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score $a_1 + a_2 + a_3 + a_4 + a_5$.

Difficulty: interview

Starter code:

Solutions:
def solve():
    n, k, z = map(int,input().split())
    lst = list(map(int,input().split()))
    maxsum = 0
    for zz in range(z+1):
        sum = lst[0]
        maxn = lst[0] + lst[1]
        if k-zz * 2 < 0:
            break
        for i in range(k-zz * 2):
            if i + 2 < n:
                maxn = max(maxn, lst[i+1] + lst[i+2])
            sum += lst[i+1]
        sum += maxn * zz
        maxsum = max(maxsum,sum)
    print(maxsum)
for i in range(int(input())):
    solve()

t = int(input())

for _ in range(t):
    n, k, z = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    best = -1
    best_pair = -1
    acc = a[0]
    used = 1

    for (prev, cur) in zip(a[:-1], a[1:]):
        used += 1

        if prev + cur > best_pair:
            best_pair = prev + cur

        acc += cur
        
        #print(f"Now k={k}, used={used}, z={z}")
        if (k - used + 2)//2 <= z and used <= k + 1:
            #print("Allowed at (prev, cur) =", (prev, cur))
            score = acc + (((k+1) - used)//2 * best_pair) + ((k+1 - used) % 2) * prev
            if score > best:
                #print(f"used={used}, (prev, cur) = {(prev, cur)}, best = {score}")
                best = score
    print(best)


for i in ' '*int(input()):
    n,k,z=map(int,input().split())
    L=list(map(int,input().split()))
    mx=sum(L[:k+1])
    sumL=[]
    for j in range(n-1):sumL.append(L[j]+L[j+1])
    for j in range(z):
        if k<=2*j+1:break
        count=max(sumL[:k-2*j-1])*(j+1)+sum(L[:k+1-2*(j+1)])
        if count>mx:mx=count
    print(mx)

import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n,k,z = map(int,input().split())
	a = list(map(int,input().split()))
	a = a[0:k+1]
	n = len(a)
	pref = [a[0]]
	for i in range(1,n):
		pref.append(pref[-1]+a[i])
	maxx = [a[0]]
	left = [k]
	start = [0]
	for i in range(1,n):
		m = z
		t = k-i
		s = pref[i]
		curr = i
		while m and t:
			if curr==i:
				curr -= 1
				m -= 1
				t -= 1
				s += a[curr]
			else:
				curr += 1
				t -= 1
				s += a[curr]
		maxx.append(s)
		left.append(t)
		start.append(curr)
	# print (maxx)
	# print (left)
	# print (start)
	ans = 0
	for i in range(n):
		ans = max(ans,maxx[i]+(pref[start[i]+left[i]]-pref[start[i]]))
	print (ans)

import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    n,k,z=MI()
    aa=LI()
    r=max(0,k-2*z)
    s=sum(aa[:r+1])
    ans=-1
    for i in range(min(n-1,k)):
        if i+1<=r:cur=s+(aa[i]+aa[i+1])*z
        else:
            s+=aa[i+1]
            left=k-i-1
            cur=s+aa[i+1]*(left//2)+aa[i]*(left-left//2)
        ans=max(ans,cur)
    print(ans)


t = int(input())

for _ in range(t):
    n, k, z = list(map(int, input().split()))
    
    a = list(map(int, input().split()))
    nei = list(a1+a2 for a1, a2 in zip(a, a[1:]))
    
    best = 0
    for lefts in range(z+1):
        rights = k - lefts
        for final_left in [False, True]:
            if rights < 1 + lefts - final_left:
                continue
            
            total = sum(a[:rights-lefts+final_left+1])
            if final_left:
                total += a[rights-lefts]
            total += (lefts - final_left) * max(nei[:rights-lefts+final_left])
            best = max(best, total)
    print(best)