Our network is under attack.It has been infected by a virus which captures the control of the server.The network topology is like
+ + + + + +
  + + + + +
    + + + +
      + + +

n : number of server in the topmost level
k : number of levels

The topmost level contains n servers, 2nd contains n-1 servers, and the k-th(lowermost) level contains n-k+1 servers.
Virus starts infecting a server only when one(or both) of the following conditions are met:

1: A neighbor of the server is completely infected.
2: Both the servers under a server in the topology are completely infected.
  * 1 *
   2 3

Here, '1' will infect when both '2' and '3' are completely infected
OR either of the neighbors '*' are completely infected with virus.

Your task is to find out the total time taken by the virus to take over the network.

Input

First line will contain 0<T<10 , the number of test cases.
For each test case, the first line contains three integers n k f:
0<n<1000 , 0<k<999 and 0<f<k
Where f is the 1-based index of server in the lowermost level which is first hit by virus.
The next k lines contain the integers denoting the time taken for the server in k-th level to be infected completely

Output

Display t lines each having the single integer, the total time after which the whole system is infected.

Example

Input:
1
7 2 3
2 3 1 7 5 9 6
4 6 5 4 7 2

Output:
33

Explanation: The infecting time of all the servers for this example are:
17 15 12 16 21 27 33
  15 11 5 9 16 18

Hence the answer 33.