P9884 [EC Final 2021] Prof. Pang and Ants

在庞教授的大房子边上，有一群包含 $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$ 秒前往冰箱并搬回食物。