题目描述

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.

题目大意

在庞教授的大房子边上，有一群包含 $m$ 只蚂蚁的蚁群，居住在有 $n$ 个洞口的洞穴里。 它们会外出寻找食物。食物在庞教授的大冰箱里，蚂蚁们试图从里面偷出食物来。

传神.jpg

特别的, 一只蚂蚁需要 $1$ 秒从任何洞口离开，并同样需要 $1$ 秒从任何洞口进入洞穴。不同的洞口有不同的位置，对一个洞口来说，它与冰箱的距离以 $a_i$ 表示，同样的，一只蚂蚁从冰箱偷出食物再到第i个洞口的时间也是 $a_i$ 秒。由于蚂蚁们技术高超，从冰箱拿出食物不会消耗它们任何时间。

每只蚂蚁都必须且只能从冰箱偷一次食物。蚂蚁可以任意选择一个洞口出发并进入任何一个洞口，前提是它们不是相同的。一个洞口在 $1$ 秒内只能有一只蚂蚁进出。因为这个原因，有些蚂蚁在偷完食物后需要等待一段时间才能进入洞口。

所以，你作为庞教授的好朋友， 需要计算出蚂蚁们偷出食物的最短时间。时间的定义为至少存在一只蚂蚁在洞穴外的时间总长，正在进出洞口的蚂蚁不被看作在洞穴里。

输入格式

第一行包括一个整数 $T~(1 \le T \le 10^5)$ ，表示测试数据的总数。

对每组测试数据：

第一行包括两个整数 $n,m$ ($1\le n \le 10^5, 1\le m \le 10^{14}$) ，分别代表洞口的总数与蚂蚁的总数。

第二行包括 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1\le a_i \le 10^9$)， 表示第$i$号洞口到冰箱的距离。

数据保证所有数据中 $n$ 的总和不超过 $5\times 10^5$.

输出格式

对每组数据，输出一行一个整数代表蚂蚁所用最短时间的秒数。

样例 #1

样例输入 #1

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

样例输出 #1

6
9
4

提示

在第三组测试数据中，蚂蚁需要 $2$ 秒通过第一个洞口进出洞穴，并需要 $2$ 秒前往冰箱并搬回食物。

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.