409955: GYM103861 M Prof. Pang and Ants

Near Prof. Pang's big house, there is an ant group which has $$$m$$$ ants and lives underground in a cave with $$$n$$$ holes. They get out of the holes for food. So where is the food? It should be in Prof. Pang's big refrigerator. The ants want to steal the food from the big refrigerator.

Specifically, for an ant, it needs $$$1$$$ second to leave from the cave through any hole and $$$1$$$ second to enter the cave through any hole. Different holes have different locations. The distance between the $$$i$$$-th hole and the refrigerator is $$$a_i$$$. Thus, after leaving the cave through the $$$i$$$-th hole, an ant needs $$$a_i$$$ seconds to go to the refrigerator. After stealing some food from the refrigerator, an ant needs $$$a_i$$$ seconds to go back to the $$$i$$$-th hole. Stealing food costs no time for the ants since they are skillful enough.

Each ant will leave the cave to steal something from the refrigerator and return to (enter) the cave after stealing. Each ant must leave the cave exactly once and then return to the cave. One ant can arbitrarily choose one hole to leave and also arbitrarily choose one hole to enter, where the two holes need not be the same. For any hole, during any second, there can be at most one ant leaving or entering the cave through it. There cannot be one ant leaving the cave and another ant entering the cave using the same hole during the same second. Because of this capacity constraint, some ants may need to wait before they leave the hole and/or before they return to the hole after stealing.

So you, Prof. Pang's good friend, need to calculate the minimum time cost for ants to achieve the goal and play a trick on Prof. Pang so that the ants can steal the food without being caught by Prof. Pang. The time cost is defined as the total length of time during which at least one ant is not in the cave. When an ant is entering or leaving the cave through some hole, it is not in the cave.

The first line contains a single integer $$$T~(1 \le T \le 10^5)$$$ denoting the number of test cases.

For each test case, the first line contains two integers $$$n,m$$$ ($$$1\le n \le 10^5, 1\le m \le 10^{14}$$$) denoting the number of the holes and the number of the ants respectively. The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1\le a_i \le 10^9$$$) denoting the time needed to get to the refrigerator from the $$$i$$$-th hole.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$5\times 10^5$$$.

For each test case, print one line containing one integer denoting the minimum time cost in seconds.

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

6
9
4

In the third test case, it takes the ant $$$2$$$ seconds to leave and enter the cave through the first hole. And it takes the ant $$$2$$$ seconds to move to the refrigerator and back to the hole.