FOODIES - ChickenLove

no tags 

A new grand chicken stall is about to open in Chennai. Buddy and Pre being close friends joined hands and planned to go for it. People have to serve themselves here in this stall.

There are N-counters available and each counter has a specified number of chicken nuggets.

The cost of each nugget being bought at any counter is same as the number of nuggets that are still remaining at the counter at that point of time (inclusive of the nugget being bought).

Pre wants to have M nuggets. As usual Buddy accepts to sponsor Pre with all his pocket money. He is so innocent that he obeys each and every order of Pre with no second thought. Pre being cunning wants Buddy to spend her too much money. So she directs buddy to buy nuggets at the counters which she says, so that he spends maximum money for her.

Of course you can't help Buddy :( But try to find him how much he would spend for Pre, if he obeys her like an IDIOT.

Input

The first line of the input contains the number of test cases, T. T test cases follow:

The first line of each test case contains an integer N, denoting the number of counters.

The next line consists of N integers: A1, A2, ... An denoting the number of nuggets available at each counter.

The next line consists of a single integer M, number of nuggets Pre wishes to have.

Output

For each test case output a single integer in a single line denoting the money that buddy would spend.

Constraints

1 <= T <= 10

1 <= N <= 100000

1 <= A1, A2 ... An <= 100000

1 <= M <= A1 + A2 + A3 + ... + An

Example

Input:
1
3
3 5 4
3

Output:
13

Explanation

Pre would ask buddy to get two nuggets from the second counter (5 + 4 = 9), and then one from the third counter (9 + 4 = 13)


hide comments
shantanu tripathi: 2015-10-21 23:05:17

silly mistakes :P.. nice1

Mohan K: 2015-10-20 16:25:08

@Anant There is no such test cases. I think that is clear from the constraints.( 1<=M<=A1+A2+A3....+An )

Anant Upadhyay: 2015-10-18 06:37:21

@Mohan k: can there be the condition such that M>total number of nuggets avialable. If so then you have not mentioned whether to print "-1" or NA or something else.

harshit sharma: 2015-10-12 19:09:18

Very Easy :)

divide_by_1: 2015-10-11 09:22:37

can someone help pls....not getting how to solve

chandan pandey: 2015-10-10 16:47:54

Priority queue not working any other ideas ?
any hint

Alex Anderson: 2015-10-10 07:59:01

Pretty simple, good practice with a standard algorithm.

Mohan K: 2015-10-08 19:29:16

@[BITMEN]DARK LORD: Your logic seems good enough.Plz check for other basic stuff. :)

[BITMEN] DARK LORD: 2015-10-08 17:51:38

don't know why my solution giving wrong answer..
plz check..solution id 15320739.

its giving right answer for every tricky case i can think off.
plz check

Mohan K: 2015-10-08 11:56:19

Few comments deleted. No spoilers please

Last edit: 2015-10-08 11:58:21

Added by:Mohan K
Date:2015-10-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem