题目描述

给定一个装置，它由 n 个首尾相接的三角形组成，这些三角形的底边都 леж在同一直线上。三角形彼此不重叠，且每两个相邻三角形恰好有一个公共顶点，这个公共顶点也在那条直线上。

这些三角形的高度依次为 h1, h2, …, hn 米。

从最左边三角形的顶点释放一个小球。小球会沿斜边滚下，再尝试爬上右边相邻三角形的斜边。

• 小球初始能量为 0。
• 每下降 1 米垂直高度，小球能量增加 ed。
• 每上升 1 米垂直高度，小球能量减少 eu。
• 坡长本身无关紧要，只看垂直高度变化。
• 如果小球在上升过程中能量变为 0，它就会停下。
• 若它到达某个三角形顶点时能量仍然 ≥ 0，则视为成功越过这个顶点，并继续向下滚动。

题目保证总满足以下两种情况之一：

• eu ≥ 2ed > 0；
• 1.5ed ≥ eu > ed > 0。

情况 2ed > eu > 1.5ed 在本题中不会出现。

各三角形的高度 hi 是非负整数（允许为 0）。你可以把任意三角形的高度增加或减少若干整数，但修改后仍必须保持非负。

请编写程序 rolling_ball，求出最小的总修改量（即所有三角形高度改变量绝对值之和），使得从最左边三角形顶点释放的小球能够“越过”所有三角形。

输入格式

第一行输入正整数 T，表示测试中的构造数量。

接下来有 T 组数据，每组包含三行：

• 第一行：一个正整数 n，表示该构造中的三角形个数；
• 第二行：n 个非负整数，表示各三角形初始高度；
• 第三行：两个正整数 ed 和 eu。

输出格式

对每组数据输出一行一个非负整数，表示使小球能够越过全部三角形所需的最小总修改量。

限制

• 1 ≤ T ≤ 10000
• 1 ≤ n ≤ 100000
• 单个测试中所有构造的 n 之和满足 ≤ 300000
• 0 ≤ hi ≤ 10000000
• 1 ≤ ed < eu ≤ 150000

子任务

只有通过某个子任务中的全部测试，才能得到该子任务的分数。

样例输入

2
4
3 2 1 5
35 38
5
4 1 3 1 1
85 102

样例输出

3
0