Banner Repair

The great crocheting festival held every year is approaching. Mr. Wincenty, who is skilled at crocheting, decided to help out his neighbors by crocheting a banner that advertises the festival. Unfortunately, he made a large mistake in the text he crocheted onto it.

His son Witek wants to help his father fix the banner. To repair it he may use only the following two operations.

• Deletion: erase one run of consecutive letters from the banner.
• Insertion: place one run of letters at the very beginning, at the very end, or between two letters of the banner.

Each operation takes $X + S \cdot Y$ minutes, where $S$ is the length of the run of letters inserted or deleted in that operation. Find the minimum total time needed to turn the initial banner text into the target banner text.

The first line contains the number of test cases $L$. The descriptions of the test cases follow.

Each test case consists of three lines.

• Line 1: an integer $D_1$ and a string $S_1$. $S_1$ is the initial banner text and $D_1$ is its length ($1 \le D_1 \le 1000$).
• Line 2: an integer $D_2$ and a string $S_2$ in the same format, where $S_2$ is the target banner text.
• Line 3: two real numbers $X$ and $Y$, each given with up to 6 digits after the decimal point ($0 \le X, Y \le 100$).

Both $S_1$ and $S_2$ consist only of uppercase English letters.

For each test case, print the minimum repair time on its own line, with 6 digits after the decimal point.