FOODIES  ChickenLove
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 Ncounters 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.
Ofcourse 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
anirudnits:
20181222 20:02:55
constraints are not correct, there are cases where M > A1+A2+..+An so take care of that and use long long int. 

viratian_070:
20170630 10:52:22
n>int wa...n>long long int ..ac....dont know why....did it in linear time 

vengatesh15:
20170119 19:12:20
did in a linear time.... 

Afrizal:
20160613 09:03:07
i really don't know why i getting WA, any tricky case?


Abhishek jaiswal:
20160419 19:04:06
It was a good question. ;)


thedictator:
20160219 17:48:10
Getting TLE on case 10 :( 

Piyush Kumar:
20151201 13:25:24
My O( N + MlogN) is giving timeout. Do I need to find a better algorithm or fast IO will work ? 

Bhargav Golla:
20151028 19:39:25
Could you tell me what is wrong with the submission 15493468? I have checked with the overflow and base cases and it works fine 

Abhay Jain:
20151022 09:52:17
AC :) Last edit: 20151025 08:47:14 

shantanu tripathi:
20151021 23:05:17
silly mistakes :P.. nice1 
Added by:  Mohan K 
Date:  20151005 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Own Problem 