回忆与展望

Problem Description

通过梦境转移器，老师成功进入了编号最大的梦境。在那里，他遇到了 Seia。她的手上有 $n$ 份回忆，编号为 $1,2,3,\cdots,n$。其中每一份都包含了老师与学生们度过的最美好的时光。这些日常时光交织在一起，共同组成了一个充满了无数奇迹的世界。 老师给编号为 $i$（$1\le i\le n$）的回忆确定了它的 美好度 $a_i$。他想要按照某个顺序重温所有的回忆，也就是确定一个 $[1,n]$ 的排列 $p$ 并依次重温编号为 $p_1,p_2,p_3,\cdots,p_n$ 的回忆。 令 $a_0=p_0=0$。老师对未来的 展望程度 可以用一个变量 $S$ 表示，初始时 $S:=0$。接下来在老师重温回忆的过程中，展望程度会根据美好度而发生变化。具体地，在老师重温编号为 $p_i$（$1\le i\le n$）的回忆时：

1. 若 $a_{p_i}>a_{p_{i-1}}$，展望程度会增加 $x$，也就是 $S:=S+x$。
2. 若 $a_{p_i}=a_{p_{i-1}}$，展望程度会增加 $y$，也就是 $S:=S+y$。
3. 若 $a_{p_i}\lt a_{p_{i-1}}$，展望程度会增加 $z$，也就是 $S:=S+z$。 Seia 通过某种方法得知了整数 $x,y,z$ 的值。她还知道老师喜欢美好， 所以 $x\ge y\ge z$ 。她想要帮助老师确定排列 $p$，使得重温所有回忆后老师的展望程度最大。 Seia 瞥见了你，此时你或许在面对着一块电脑屏幕编写着代码，又或许是面对着一张草稿纸沉思。你或许正重温着以前某一次竞赛的试题，又或许对着一个极为重要的竞赛成绩感到懊恼。其实，她更建议你在竞赛结束后与你的同学们聊聊天，留意留意这个世界的某处角落，回忆回忆过去，展望展望未来。你可能在某一天突然发觉，竞赛的具体知识和最终结果变得不再重要，而那份美好的回忆才是你人生中无法抹去的奇迹。 现在，是时候将这个问题告诉你了，Seia 想道。 你只需要告诉她展望程度的最大值。

Input

本题包含多组测试数据。 来自 Seia 的温馨提示：本题输入输出量较大，对于使用 C++ 语言参加竞赛的选手，强烈建议使用关闭同步流的 cin 和 cout 完成输入输出。 首先在第一行输入一个整数 $T$（$1\le T\le100$）表示测试数据组数。 对于每一组测试数据，输入包含两行。 第一行包含四个整数 $n,x,y,z$（$1\le n\le\sum n\le5\times10^6$，$1\le z\le y\le x\le 5\times10^6$），表示回忆的数量和计算展望程度所需要的三个参数。 第二行包含 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n$（$1\le a_1,a_2,a_3,\cdots,a_n\le n$）表示回忆的美好度。

Output

对于每一组测试数据，输出包含一行一个整数表示展望程度的最大值。

Sample Input

2
5 9 7 5
3 1 2 3 4
10 1919810 114514 1
2 3 5 9 10 10 2 2 5 4

Sample Output

43
15472995

Hint

在样例的第一组测试数据中，取 $p_1=2,p_2=3,p_3=1,p_4=4,p_5=5$ 时展望程度为 $43$，达到最大值。具体地：

1. 由于 $a_2>a_0$，因此 $S:=9$。
2. 由于 $a_3>a_2$，因此 $S:=18$。
3. 由于 $a_1>a_3$，因此 $S:=27$。
4. 由于 $a_4=a_1$，因此 $S:=34$。
5. 由于 $a_5>a_4$，因此 $S:=43$。 存在其他达到最大值的排列，在此仅列举其中一个。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）