FOR THIS CODE USING PREFIX SUM

Jojo's Hardest Problem (?) Jojo is enjoying his vacation with his family. Suddenly an instant message came in. Apparently there is a message from Lili : Jojo, dont forget to check the forum. Who knows if there is an assignment before the exam Jojo finally took the time to check the discussion forum and sure enough, there were some assignments given to his class. He immediately told his classmates. Jojo finds out one difficult problem for himself as follows. Given an array contains N elements and also given an integer M. You need to find a value of a function f (x, k ) so that the function has value as maximum as possible but still less than or equal to M. Value of k is arbitrary as the value less than or equal to N. The function f(x, k) is expressed as below

f(x, k) = A [ x ] k + A [ x + 1] ( k 1) + ... + A [ x + k 1] 1

Help Jojo get the right final answer

Format Input

Input consists of an integer T that indicates the number of test case. Then, 3 lines follow. The first line contains an integer N as the number of elements in array. The next one is describing the value N elements A [ i] in the array and followed by an integer M on the third line.

Format Output

Output should be a single integer Y , the maximum value of function f (x, k) such k arbitrary value that less than or equal to N.

Constraints

1 N 4 10 ⁵ 1 A [ i ] 10 ⁶ 1 M 10¹²

Sample Input 1 (standard input)

5 6 1 3 4 6 10

Sample Output 1 (standard output)

10

Sample Input 2 (standard input)

5 1 2 3 4 5 14

Sample Output 2 (standard output)

13

Explanation

For test case 1, the maximum result is f(3, 2) = 3 2 + 4 x 1 = 10

DO IN C

DO NOT USE HEADER INCLUDE STDIO.H