Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3925
Magian

Time Limit: 6 Seconds      Memory Limit: 65536 KB

ことみ(Kotomi) is a hardworking girl and always stays at library.

One day, Kotomi got a magic book in the library and following the direction of the book, she reached a cave. In the cave, there were n stones on the wall, either painted in red or blue. The book said that behind one of the stones there are lots of treasure. Smart Kotomi had two skills. One was to change the color of a stone, and that cost her K MPs(Magic points). The other skill was to destroy a stone with corresponding MPs, that is to say, if she destroyed the red stone that on the ith place, it will cost her Ri MPs, and if she destroyed the blue stone that on the ith place, it will cost her Bi Mps. Once she destroyed the stone where the treasure hid, she would got the treasure, otherwise, the fragment of the stone would told her some information. The red stone fragment would tell you whether the treasure is on the left of this stone and the blue stone fragment would tell you whether the treasure is on the right of this stone.

But MPs were precious, so Kotomi wanted to use as few as she can. Now, she wanted to know how many MPs should she use to find the treasure in the worst case.

Input

The first line of input is a integer T(1 ≤ T ≤ 50), the number of cases.

For each case, there are four lines.

The first line has two integers, n and K (1 ≤ n ≤ 1000 , 0 ≤ K ≤ 1000000).

The second line has n integers Ri (1 ≤ in), (0 ≤ Ri ≤ 1000000).

The third line also has n integers Bi (1 ≤ in), (0 ≤ Bi ≤ 1000000).

The fourth line has n chars, represent for the initial color of the stones from 1 to n. 'R' for red and 'B' for blue.

Output

T lines, each line for an integer that is the minimum MPs Kotomi should use in the worst case.

Sample Input

1
5 0
1 1 1 1 1
1 1 1 1 1
RBRBR

Sample Output

3

Author: JIN, Mengge
Source: ZOJ Monthly, February 2016
Submit    Status