#P18380. Traveling in Cells 3

Traveling in Cells 3

Traveling in Cells 3

题目描述

小青鱼王国可以看成一条由 2×10100+12\times10^{100}+1 个格子组成的直线,格子的编号依次为 −10100,−10100+1,…,10100-10^{100},-10^{100}+1,\ldots,10^{100}。

小青鱼要为下一届 Universal Cup 总决赛选择举办地点。目前有 nn 支获得参赛资格的队伍,第 ii 支队伍位于编号为 xix_i 的格子。所有队伍都要前往同一个举办格子。

王国中有两种交通方式,可以任意组合使用:

  • 铁路:从格子 ii 移动到相邻格子 i−1i-1 或 i+1i+1,每次花费 11 美元。
  • 航班:从格子 ii 移动到格子 i−ai-a 或 i+ai+a,每次花费 bb 美元。

举办地点可以选择王国中的任意一个格子,不要求已有队伍位于该格子。小青鱼只关心总花费,不关心旅行时间。

请最优地选择举办地点及每支队伍的旅行方式,使所有队伍抵达举办地点的总花费最小,并输出这个最小值。

输入格式

第一行一个整数 TT(T≥1T\ge1),表示测试用例数。

每个测试用例包含两行:

  • 第一行三个整数 n,a,bn,a,b,其中 n≥1n\ge1,1≤a,b≤10121\le a,b\le10^{12}。
  • 第二行 nn 个整数 x1,x2,…,xnx_1,x_2,\ldots,x_n,其中 −1012≤xi≤1012-10^{12}\le x_i\le10^{12}。队伍的位置可以重复。

保证一个输入文件中所有测试用例的 nn 之和不超过 3×1053\times10^5。

输出格式

每个测试用例输出一行,一个整数,表示最小总花费。

样例输入 1

3
3 5 1
1 11 22
4 5 3
1 3 5 8
7 6 3
2 9 15 24 33 40 53

样例输出 1

5
7
55

样例说明

对第一个测试用例,可在编号 1111 的格子举办比赛:

  • 位于 11 的队伍乘坐两次航班:1→6→111\to6\to11,花费 22。
  • 位于 1111 的队伍无需移动,花费 00。
  • 位于 2222 的队伍先乘坐两次航班,再乘坐一次铁路:22→17→12→1122\to17\to12\to11,花费 33。

总花费为 2+0+3=52+0+3=5。下图为旅行路线示意。

样例旅行路径,举办格子为11