N. Spectacular Seal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

They call him the Seal, not because he swims, but because every case he touches gets closed. Stamped shut. Sealed. A few miles up the coast from Aqua Badran sprawls Aquarbour, a city so overcrowded that three people can witness a murder and all swear they were looking the other way. Last Tuesday, someone walked into the Aquarbour National Archive and walked out with the Ledger, a book the city's elite would very much prefer remained unread. The Seal took the case for one shawarma sandwich and a cup of Al Ameed coffee. His only lead: the thief left behind two coded sequences, scratched into the marble floor in two parallel rows.

  • Row $$$a$$$ contains $$$n$$$ marks bearing each odd number from $$$1$$$ to $$$2n$$$, in some order.
  • Row $$$b$$$ contains $$$n$$$ marks bearing each even number from $$$1$$$ to $$$2n$$$, in some order.
The Seal knows the cipher. The thief's identity is revealed only when row $$$a$$$ reads lexicographically smaller than row $$$b$$$. Anything else, and the marble stays silent. ("Cute," the Seal muttered. "A puzzle with a sense of drama.") He can rearrange the marks himself, but the marble is old and brittle. Each operation is:
  • choose one of the two rows,
  • pick an index $$$i$$$ from $$$1$$$ to $$$n-1$$$,
  • swap the marks at positions $$$i$$$ and $$$i+1$$$ of that row.
The two rows weren't carved equally:
  • Row $$$a$$$ was cut into soft limestone, each swap costs $$$c_a$$$ units of effort.
  • Row $$$b$$$ was cut into hard Aquarbour granite, each swap costs $$$c_b$$$.
The Seal has until sunrise. He needs the minimum total effort to make the marble talk. For two different arrays $$$x$$$ and $$$y$$$ of the same length $$$n$$$, $$$x$$$ is lexicographically smaller than $$$y$$$ if, at the first position where they differ, $$$x$$$ has the smaller element.
Input

The first line contains $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of cases on the Seal's desk. For each test case:

  • The first line contains three integers $$$n$$$, $$$c_a$$$, $$$c_b$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le c_a, c_b \le 10^9$$$).
  • The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$, all odd, pairwise distinct, each between $$$1$$$ and $$$2n$$$.
  • The third line contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$, all even, pairwise distinct, each between $$$1$$$ and $$$2n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Output

For each test case, print one integer, the minimum effort the Seal must spend before the marble gives up its name.

Example
Input
3
2 1 1
3 1
4 2
3 1 3
5 3 1
2 4 6
4 4 3
7 5 3 1
2 6 4 8
Output
0
2
7
Note

Case 1. The marble is already talking ($$$3 \lt 4$$$). The Seal lights a cigarette and writes the name down. Cost: $$$0$$$. Case 2. Granite is unforgiving ($$$c_b = 3$$$). The Seal works only the limestone row, sliding $$$1$$$ to the front of row $$$a$$$ in two swaps: $$$[1, 5, 3]$$$, which already reads smaller than $$$[2, 4, 6]$$$. Cost: $$$2 \cdot 1 = 2$$$. Case 3. Now both chisels come out. One swap on row $$$a$$$ (cost $$$4$$$) brings $$$5$$$ to the front: $$$[5, 7, 3, 1]$$$. One swap on row $$$b$$$ (cost $$$3$$$) brings $$$6$$$ to the front: $$$[6, 2, 4, 8]$$$. Since $$$5 \lt 6$$$, the marble confesses. Total cost: $$$4 + 3 = 7$$$.