ZB loves playing StarCraft and he likes Zerg most!

One day, when ZB was playing SC2, he came up with an idea:

He wants to change the queen's ability, the queen's new ability is to choose a worker at any time, and turn it into an egg, after K units of time, two workers will born from that egg. The ability is not consumed, which means you can use it any time without cooling down.

Now ZB wants to build N buildings, he has M workers initially, the i-th building costs t[i] units of time, and a worker will die after he builds a building. Now ZB wants to know the minimum time to build all N buildings.

Input

The first line contains an integer T, meaning the number of the cases. 1 <= T <= 50.

For each test case, the first line consists of three integers N, M and K. (1 <= N, M <= 100000, 1 <= K <= 100000).

The second line contains N integers t[1] ... t[N](1 <= t[i] <= 100000).

Output

For each test case, output the answer of the question.

Sample Input

2
3 1 1
1 3 5
5 2 2
1 1 1 1 10

Sample Output

6
10

Hint

For the first example, turn the first worker into an egg at time 0, at time 1 there’s two worker. And use one of them to build the third building, turn the other one into an egg, at time 2, you have 2 workers and a worker building the third building. Use two workers build the first and the second building, they are built at time 3, 5, 6 respectively.

题意：给你n个建筑，m个人，人有一个特异功能， 可以一分为二，但需要花费k的时间，然后给你 每个建筑建造完所需时间

问建造完这n个建筑最短需要多少时间

思路：如果m>=n 直接输出最大的那一个时间

如果m<n,则需要n-m次分裂，也就是要找那两个建筑是由同一个人分裂建造的

比如n=4，m=2，k=2

3 5 7 9

这个过程其实就是一个哈夫曼树的应用，

用小顶堆实现就可以了

这样最后就化成了m个人建造m个建筑，最后O（m）跑一遍取最大值就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;
const int maxn=1e5+5;
int main()
{
    priority_queue<int,vector<int>,greater<int> > q;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,k,a;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)
            scanf("%d",&a),q.push(a);
        while(n>m)
        {
            q.pop();
            a=q.top();
            q.pop();
            q.push(a+k);
            n--;
        }
        while(q.size()!=1)
        {
            q.pop();
        }
        printf("%d\n",q.top());
        q.pop();
    }
    return 0;
}