F. Toll Road
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A new shiny triple-A class toll highway from Moscow to Saint-Petersburg is about to open soon. Of course, this highway is bi-directional, but for the purpose of this problem we only consider direction from Moscow to Saint-Petersburg as the one all participants of this competition would like to travel in late November.

The road will be of length $$$L$$$ (in some specific units of distance who wished to remain anonymous) and will have $$$n$$$ special points. All special points are located at some distinct integer coordinates along the road, with one of them being located at position $$$0$$$ and one at position $$$L$$$. Each special point is either an entrance or an exit. Of course, special point at position $$$0$$$ is an entrance and special point at position $$$L$$$ is an exit.

Each car that uses the highway will be equipped with a special device called transponder. The owner of the road will place toll gates at some positions along the road to communicate with transponders of cars passing by. There are two types of gates that can be built along the road.

  1. Entrance or exit gates. They can only be built at positions that contain an entrance or an exit. Such gate costs $$$a$$$ burles to build and communicates with transponders of all cars that use corresponding entrance or exit.
  2. Road gates. They can be built only at half-integer positions, i.e. points $$$k + 0.5$$$ for all $$$k$$$ from $$$0$$$ to $$$L - 1$$$. Such gate costs $$$b$$$ burles and communicates with transponders of all cars passing by along the highway.

In order to properly charge all cars that use the highway, one needs to be able to identify the exact entrance position and the exact exit position for each of these cars. Formally, you need to build a set of gates to satisfy the following requirements.

  1. Each car that enters the road at some entrance, goes forward and then takes some exit should pass near at least one of the gates, so we can identify that this car was using the highway.
  2. For each car that enters the road at some entrance, goes forward and then takes some exit we should be able to exactly tell the position of the entrance and the position of the exit based on the information from communication between this car's transponder and toll gates. Note that due to complicated tariffs we are interested in exact positions of the entrance and the exit, not just the distance travelled along the highway.
  3. The total cost of all gates built should be minimum possible.
Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of tests to process in this input. Then follow $$$t$$$ tests' descriptions.

The description of each test starts with four integers $$$n$$$, $$$L$$$, $$$a$$$ and $$$b$$$ ($$$2 \leq n \leq 500\,000$$$, $$$1 \leq L, a, b \leq 10^9$$$), the number of special points along the highway, the length of the highway, the cost of building one gate at entrance or exit, and the cost of building one gate along the road respectively. Each of the next $$$n$$$ lines contains a character $$$c_i$$$ and an integer $$$x_i$$$ ($$$0 \leq x_i \leq L$$$), separated by a single space. The character $$$c_i$$$ denotes the special point type and is either 'E' (entrance) or 'T' (exit), while $$$x_i$$$ means the position of this point along the road. It is guaranteed that all $$$x$$$'s are distinct, and there is an entrance at position $$$0$$$ and an exit at position $$$L$$$.

It is guaranteed that sum of $$$n$$$ over all tests won't exceed $$$500\,000$$$.

Output

For each test print one integer on a separate line, the minimum total cost of building a set of gates that gives a full control of movements of all cars along the highway.

Example
Input
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
Output
1
2
15
28