Public submissions
Source code of every submission to this problem in this contest will be visible for everyone since 2015-11-29 19:30:00.

HELPBTW - Help BTW

BTW wants to buy a gift for her BF and plans to buy an integer array. Generally Integer arrays are costly and hence bought the cheapest one from the market. Her BF is very judgemental and assess the quality of the array by just looking at the smallest element in the array. Hence, she decided to improve the quality of the array. Increment operation on array elements are very costly and would take ONE FULL DAY to complete. Also, Increment operations can be done in parallel on at most M consecutive array elements. She only has K days left. Help BTW calculate the maximum possible “quality” of the array she can attain.

(BTW BTW is the name of the character :P )

Input

Very first line contains T – (number of test cases)

First line in each test case contains N – (size of the array BTW has bought from the market), M, K (days left)

Second line in each test case contains N integers (values of the initial array BTW bought from the market)

Output

Print the maximum possible “quality” she can attain.

Constraints

1<=T<=100

1<=N<=10^5

0<=M<=N

0<=K<=10^9

0<=Values of array<=10^9

Example

Input
2
3 2 1
2 2 3
3 2 1
2 3 2

Output
3
2

Added by:Noob
Date:2015-11-28
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA
Public source code since: 2015-11-29 19:30:00

hide comments
2015-11-28 21:12:26 Mohan K


Last edit: 2015-11-28 21:12:47
2015-11-28 16:42:22 Noob
Constraints Added!
2015-11-28 16:38:41 Keshav Reddy
What are the constraints?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.