题目描述

在辛逝纪30年，芙莉莲一行人在旅途中遇到一处三千公尺的大断崖。断崖中有 \(n\) 个高度不一的木桩，从左到右依次排列，高度用数组 \(a\) 表示。 直接飞过去会消耗过多魔力，幸好芙莉莲有一本可以搭桥的魔导书。她可以通过消耗魔力来调整木桩的高度，然后搭建一座桥。芙莉莲想知道，最少需要消耗多少魔力才能成功抵达对岸。

给定一个长度为 \(n\) 的序列 \(a_1, a_2, \dots, a_n\)，代表木桩的原始高度。芙莉莲需要选择一个整数 \(r\) \((1 \le r \le n)\)，并施展魔法建造一座连接第 \(1\) 根到第 \(r\) 根木桩的桥。为了使桥梁结构合法，必须满足以下条件：

• 通过魔法调整，使得第 \(1\) 根和第 \(r\) 根木桩的最终高度均为 \(V\)；
• 对于所有 \(i \in [1, r]\)，第 \(i\) 根木桩的最终高度 \(a'_i\) 不得超过 \(V\)。

芙莉莲可以任意次地调整木桩的高度，每次调整可以选择一个木桩 \(i\)：

• 将其高度增加 \(1\)，消耗 \(x\) 点魔力；
• 将其高度减少 \(1\)，消耗 \(y\) 点魔力。

在搭建完成后，剩余的 \((n - r)\) 个单位路程需要通过飞行魔法通过，每往右移动一单位距离固定消耗 \(k\) 点魔力。请你帮助芙莉莲计算出最小魔力消耗。

输入格式

第一行包含一个整数 \(T\)，表示测试用例的数量。对于每个测试用例：第一行包含四个整数 \(n, x, y, k\)。第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)。

其中 \(1 \le T \le 10\)， \(1 \le n, x, y \le 10^5\)， \(1 \le a_i, k \le 10^9\)，每组数据的 \(\sum a_i \le 10^{13}\)。保证所有测试用例的 \(n\) 之和不超过 \(2 \cdot 10^5\)。

输出格式

输出一行一个整数，表示芙莉莲抵达对岸所需的最小魔力消耗。

样例输入

1
5 10 5 100
10 20 30 20 10

样例输出

200