B'Marisa comes to pick mushrooms in the Enchanted Forest. The Enchanted forest can be represented by n points on the X -axis numbered 1 through n . Before Marisa started, her friend, Patchouli, used magic to detect the initial number of mushroom on each point, represented by a_1,a_2, ldots,a_n . Marisa can start out at any point in the forest on minute 0 . Each minute, the followings happen in order: Note that she cannot collect mushrooms on minute 0 . Now, Marisa wants to know the maximum number of mushrooms she can pick after k minutes. Each test contains multiple test cases. The first line contains a single integer t ( 1 <= q t <= q 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two integers n , k ( 1 <= n <= 2 cdot 10 ^ 5 , 1 <= k <= 10^9 ) -- the number of positions with mushrooms and the time Marisa has, respectively. The second line of each test case contains n integers a_1,a_2, ldots,a_n ( 1 <= a_i <= 10^9 ) -- the initial number of mushrooms on point 1,2, ldots,n . It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10 ^ 5 . For each test case, print the maximum number of mushrooms Marisa can pick after k minutes. Test case 1: Marisa can start at x=2 . In the first minute, she moves to x=1 and collect 5 mushrooms. The number of mushrooms will be [1,7,2,3,4] . In the second minute, she moves to x=2 and collects 7 mushrooms. The numbers of mushrooms will be [2,1,3,4,5] . After 2 minutes, Marisa collects 12 mushrooms. It can be shown that it is impossible to collect more than 12 mushrooms. Test case 2: This is one of her possible moving path: 2 rightarrow 3 rightarrow 2 rightarrow 1 rightarrow 2 rightarrow 3 rightarrow 4 rightarrow 5 It can be shown that it is impos'...