Description
KonoSuba: Kazuma's Stealing on this Wonderful World!
Kazuma is an adventurer who is good at stealing, a skill he learned from "his friend" Chris. One day, he stole a stack of n enchanted gloves from the Devil King's army. However, the gloves are mismatched in some way. To sell all the gloves in pair, Kazuma wants to ask his friend Wiz to correct the gloves (in a price, of course).
(Kazuma and Chris)
(Wiz)
Given a stack of n gloves, Kazuma wants to correct the gloves so that they make exactly n/2 matching pairs. Kazuma found out that there are l left-handed glove and r right-handed glove in the stack. Also, each single glove is equipped with a gem gi. Note that a left-handed glove and a right-handed glove with the same gem form a matching pair.
Kazuma can pay Wiz c Eris (currency) to perform one of the following correction:
- Turn the gem on a glove into another gem
- Turn a left-handed glove into a right-handed glove
- Turn a right-handed glove into a left-handed glove
Wiz can perform arbitrary number of corrections for Kazuma (because Wiz is a powerful lich with overwhelming mana). Note that the gem doesn't changed if we turn a left-handed glove into a right-handed glove, and vice versa.
Kazuma want to spend as little Eris as possible. Although Kazuma has intelligence above average, he still can not find the optimal way to correct the gloves, not to mention any of his party members - Aqua, Megumin, and Darkness. Write a program to help Kazuma with his problem. In return, maybe he can teach you how to perform steal "correctly".
In this problem, each test case contains multiple cases. Each case is independent. You need to output one answer per each case.
Credit: This problem is adated from Phoenix and Socks.
Input
The first line contains an integer T, representing the number of cases.
The first line of each case contains four integer n, l, r and c, representing the number of gloves, the number of left-handed gloves, the number of right-handed gloves, and the cost of each correction.
The second line of each case contains n integer g1, g2, ..., gn, representing the gem equipped on each glove.
It is guaranteed that:
- n is even
- 0 ≤ l, r ≤ n
- l + r = n
- 1 ≤ gi ≤ 109
- Test case #1: Sample Input
- Test case #2-6: 1 ≤ T ≤ 100, 1 ≤ n ≤ 2×103, 1 ≤ c ≤ 105, the sum of n among all cases ≤ 2×103
- Test case #7-10: 1 ≤ T ≤ 103, 1 ≤ n ≤ 2×105, 1 ≤ c ≤ 109, the sum of n among all cases ≤ 2×105
Output
For each case, output the minimum Eris Kazuma need to spend to correct the gloves with a new line symbol.