409070: GYM103430 C Athletes

A wrestling club trains $$$n$$$ athletes. Each of them specializes either in algorithmic sambo (referred below as sport A), or in berland jiu-jitsu (referred below as sport B). In addition, each athlete has a certain level of skill.

Thus, the $$$i$$$-th athlete is characterized by two parameters: $$$t_i$$$ — a sport (either A or B) and an integer skill level $$$f_i$$$ ($$$-10^6 \le f_i \le 10^6$$$).

If an athlete from sport A competes in B, then their skill level is reduced by a given number $$$x$$$ (the value does not depend on a particular athlete). Similarly, if an athlete from sport B competes in A, then their skill level is reduced by a given number $$$y$$$ (again, the value does not depend on a particular athlete).

The club plans to participate in a competition. To participate, it is required to set up $$$k$$$ ($$$2k \le n$$$) teams of two athletes in each — one of them will compete in sport A, the other will compete in sport B. Of course, no athlete can be included in more than one team.

Your task is to compose $$$k$$$ teams in such a way that the total skill of all participating athletes in these teams is maximum possible. Formally, it is necessary to form $$$k$$$ teams from the $$$n$$$ given athletes, in each team there should be one athlete competing in A and one athlete competing in B. If an athlete competes in a sport they don't specialize in, then their skill decreases by $$$x$$$ (if an athlete with $$$t_i$$$ = A competes in B) or by $$$y$$$ (if an athlete with $$$t_i$$$ = B competes in A).

Print the maximum possible sum of skill levels of athletes in $$$k$$$ teams if the club forms teams in an optimal way. Remember that an athlete's skill level is reduced (by $$$x$$$ or $$$y$$$ depending on the sport) if they are playing in a sport that is different from their specialization.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. The following are $$$t$$$ test cases.

The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$x$$$, $$$y$$$ ($$$2 \le n \le 2\cdot10^5$$$; $$$1 \le k \le \frac{n}{2}$$$; $$$1 \le x,y \le 10^6$$$), where:

• $$$n$$$ is the number of athletes in the club,
• $$$k$$$ is the required number of teams,
• $$$x$$$ is how much the skill level of an athlete of sport A decreases if they compete in sport B,
• $$$y$$$ is how much the skill level of an athlete of sport B decreases if they compete in sport A.

Each of the next $$$n$$$ lines contains a value $$$t_i$$$ (either the character A or the character B) and an integer $$$f_i$$$ ($$$-10^6 \le f_i \le 10^6$$$) — the sport of the $$$i$$$-th athlete and their skill level, respectively.

It is guaranteed that the sum of all values of $$$n$$$ for all test cases in the input does not exceed $$$2\cdot10^5$$$.

For each of the $$$t$$$ test cases, print one integer — the maximum total skill of the athletes of $$$k$$$ teams, if in each team one athlete will compete in sport A, and the other will compete in sport B. Remember that if an athlete competes in a sport they don't specialize in, then their skill level is reduced.

4
4 1 1 2
A 10
B 10
B 20
B 15
4 1 1 100
A 10
B 10
B 20
B 15
4 2 1 1
A 10
B 10
B 20
B 15
4 2 1 23
B 1
B 9
B -3
A 5

33
30
54
-11