One day, Xiao Ming accidentally picked up a magic lamp. The lamp god said to Xiao Ming that he could satisfy his wish. Xiao Ming made a wish to the lamp god to make himself more handsome, so the lamp god promised him.
But the lamp god did not simply realize this wish for him. He gave Xiao Ming a sequence A containing n integers, and let him pick m numbers in A. The sum of the m numbers is handsome value which Xiao Ming will finally get.
Of course, Xiao Ming definitely thinks that the higher the handsome value, the better, but things are not so simple, the exact rules are defined as follows:
1. Xiao Ming selected a sequence b, b1, b2, b3 … bm (bi denotes the subscript in A, 1<=b1<b2<b3<… <bm<=n)
2. Any b[i] must satisfy b[i-1]+k>=b[i].(1<i<=m)
3. Xiao Ming's handsome value S=A[b1]+A[b2]+A[b3]+...+A[bm]
For the stupid Xiao Ming, he can only pick m number randomly, but he wants to get the most handsome value, so he asked you to help. Can you help him?
Hang：这题我不会翻译
The first line contain an integer t indicates the number of questions asked (1 <= t <= 20).
Next, the first line of each query contains two spaces separated by an integer n, m, k.
The next n integers are the n integers of sequence A.
(1<=k,m<=n<=3000. 0<=A[i]<=1e5)
(guarantee all inquiries ∑n<=3000)
For each query, output a line of integers indicating the value of the maximum handsome value.
2 5 2 2 20 1 18 2 19 13 4 3 10 0 0 0 8 0 0 0 9 0 0 0 7
38 19