Practice Season

Two professional baseball teams, X and Y, spend a practice season visiting 7 cities in a fixed order. The 7 cities are labeled c1, c2, c3, c4, c5, c6, c7. Both teams must start the practice season on the same day and finish it on the same day.

During the practice season, each day a team either visits one city to train or checks into a hotel and rests for the whole day (a rest day). The order of cities each team must visit is already fixed and cannot be changed, but rest days may be inserted freely wherever it helps.

For example, if a team's order of cities is S = <c1, c2, c3, c1, c4, c1, c5, c4>, rest days R can be inserted to produce new schedules such as:

• S1 = <c1, c2, R, c3, c1, R, R, c4, c1, c5, R, c4>
• S2 = <R, R, c1, c2, c3, c1, R, c4, R, c1, c5, c4>

Stadium fee. Training at a stadium costs $C$ for a team, the same for all 7 cities. If both teams X and Y use the same stadium on the same day, the total is $C$, so each team pays only $C/2$, which is cheaper. If they train at different stadiums, each pays $C$, for a total of $2C$.

Hotel fee. On a rest day a team rents an entire hotel. Renting incurs a one-time exclusive-use fee $D$, plus a per-day charge $d$ for the length of the stay. That is, staying $w$ consecutive days at a hotel costs $D + w \cdot d$. For example, with $D = 4$ and $d = 1$, staying 5 consecutive days costs $4 + 1 \cdot 5 = 9$, whereas staying on 5 separate days pays the exclusive fee five times plus five days of charges, for $5 \cdot 4 + 5 \cdot 1 = 25$.

If both teams keep their visiting orders with no adjustment, the schedule is Table 1. Here team Y rests on the last two days (days 7 and 8) so that it starts and ends together with team X.

Table 1. Simple schedule A

With stadium fee $C = 3$, hotel exclusive fee $D = 4$, and daily fee $d = 1$, following Table 1 costs the two teams as shown in Table 2.

Table 2. Cost of schedule A

So the total cost is $6 \cdot 6 + 8 + 4 = 48$. Now consider a slightly different schedule. As in Table 3, inserting rest days into team Y's schedule increases the number of days the two teams share a stadium, lowering the total cost.

Table 3. Schedule B

Here the total cost is $3 \cdot 6 + 8 \cdot 2 = 34$, saving $48 - 34 = 14$ compared with schedule A. Note that the optimal schedule can differ depending on the values of $C$, $D$, and $d$.

Given the orders of cities visited by teams X and Y, find the best schedule that minimizes the sum of the two teams' costs, and print that minimum total cost.

Input is given on standard input. The first line contains the number of test cases $T$. Each test case consists of three lines.

• The first line contains integers $C$, $D$, and $d$ separated by single spaces. All three are positive integers not greater than 10.
• The next two lines give the order of cities visited by team X and by team Y, respectively, separated by single spaces, with the end of each line marked by the number 0. Each city is an integer from 1 to 7.

The number of cities $N$ satisfies $2 < N < 100$.

For each test case, print on its own line the minimum cost to complete the practice season (the sum of X's and Y's costs).