一条从莫斯科到圣彼得堡的全新三A级收费公路即将开通。当然，这条公路是双向的，但为了解决本题，我们仅考虑从莫斯科到圣彼得堡的方向，这也是本场比赛所有参赛者在十一月下旬想要前往的方向。

公路长度为 $L$（单位为某种不便透露的距离单位），沿途有 $n$ 个特殊点。所有特殊点都位于公路沿线不同的整数坐标上，其中一个点位于位置 $0$，另一个点位于位置 $L$。每个特殊点要么是入口，要么是出口。当然，位置 $0$ 处的特殊点是入口，位置 $L$ 处的特殊点是出口。

每辆使用该公路的汽车都将配备一种称为应答器的特殊设备。公路所有者将在公路沿线的某些位置设置收费站，以与经过的汽车的应答器进行通信。沿公路可以建造两种类型的收费站：

1. 入口或出口收费站。它们只能建在包含入口或出口的位置。建造这种收费站的成本为 $a$ 伯尔，并与使用相应入口或出口的所有汽车的应答器进行通信。
2. 公路收费站。它们只能建在半整数位置，即对于从 $0$ 到 $L-1$ 的所有 $k$，点 $k + 0.5$ 处。建造这种收费站的成本为 $b$ 伯尔，并与沿公路行驶的所有汽车的应答器进行通信。

为了正确地向所有使用该公路的汽车收费，需要能够识别每辆车的确切入口位置和确切出口位置。形式上，你需要建造一组收费站以满足以下要求：

1. 每辆在某个入口进入公路、向前行驶并从某个出口驶出的汽车，都必须经过至少一个收费站附近，以便我们识别出该车正在使用公路。
2. 对于每辆在某个入口进入公路、向前行驶并从某个出口驶出的汽车，根据其应答器与收费站之间的通信信息，我们应该能够准确地判断出其入口位置和出口位置。请注意，由于复杂的资费标准，我们关心的是入口和出口的确切位置，而不仅仅是沿公路行驶的距离。
3. 所有建造的收费站的总成本应尽可能低。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示需要处理的测试用例数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的描述以四个整数 $n, L, a, b$ ($2 \le n \le 500\,000, 1 \le L, a, b \le 10^9$) 开头，分别表示公路沿线的特殊点数量、公路长度、建造一个入口或出口收费站的成本，以及建造一个公路收费站的成本。接下来的 $n$ 行，每行包含一个字符 $c_i$ 和一个整数 $x_i$ ($0 \le x_i \le L$)，中间用空格隔开。字符 $c_i$ 表示特殊点的类型，为 ‘E’（入口）或 ‘T’（出口），$x_i$ 表示该点沿公路的位置。保证所有 $x$ 互不相同，且位置 $0$ 处有一个入口，位置 $L$ 处有一个出口。

保证所有测试用例的 $n$ 之和不超过 $500\,000$。

输出格式

对于每个测试用例，在单独的一行中输出一个整数，表示能够完全控制所有汽车在公路上的行驶轨迹所需的收费站建设总成本的最小值。

样例

输入 1

4
2 10 1 1
E 0
T 10
2 10 3 2
E 0
T 10
5 40 5 6
E 0
T 40
T 20
E 30
E 10
10 9 5 6
T 5
E 6
T 7
E 8
T 9
E 0
T 1
E 2
T 3
E 4

输出 1

1
2
15
28