Fixing Disks

You are playing a game with a stack of $N$ disks. The goal is to remove every disk from your stack. Each removal has a cost, and you want the total cost to be as small as possible.

Every disk carries a label $L$, and $1 \le L \le 20$.

You also get a Master stack of $N$ disks to help you clear your own stack.

There are two ways to remove the disk on top of your stack.

1. Remove the top disk of your stack on its own. If its label is $c$, the removal costs $c$.
2. Remove the top disk of the Master stack together with the top disk of your stack. This is allowed only when the two labels are equal, and it costs nothing.

You may also reorder the top $K$ disks of your stack. Immediately after each reorder you must remove the top disk, so one removal is preceded by at most one reorder. A reorder applies to a range of disks at the top of your stack, and the size of that range cannot exceed the number of disks still on the stack. Three reorders are allowed.

1. Reverse. Reverse the order of the top $r$ disks ($2 \le r \le K$). If those disks are $d_1, d_2, \ldots, d_r$ read from the top down, then after the operation they read $d_r, \ldots, d_2, d_1$ from the top down. One reverse costs $R$.
2. Cyclic shift up. Shift up by one inside the top $u$ disks ($2 \le u \le K$). If the top four disks read $d_1, d_2, d_3, d_4$ from the top down, an up shift over the top three gives $d_2, d_3, d_1, d_4$, and an up shift over all four gives $d_2, d_3, d_4, d_1$. One up shift costs $U$.
3. Cyclic shift down. Shift down by one inside the top $d$ disks ($2 \le d \le K$). If the top four disks read $d_1, d_2, d_3, d_4$ from the top down, a down shift over the top three gives $d_3, d_1, d_2, d_4$, and a down shift over all four gives $d_4, d_1, d_2, d_3$. One down shift costs $D$.

If the reorder leaves the top of the Master stack and the top of your stack carrying the same label, the pair comes off for free. Rule 1 is still available in that case, so you may instead pay the label and remove only your own disk. When the labels differ, rule 1 is the only option.

One more rule constrains the order of removals. Number the levels of your stack starting at $0$ for the bottom. When the disk that started at level $j$ is removed, every disk that started at level $j + M$ or higher must already be gone.

Find the minimum total cost of emptying your stack.

The first line contains six space separated integers $N$, $K$, $M$, $D$, $U$, $R$.

• $N$ ($1 \le N \le 100$) is the number of disks in each stack.
• $K$ ($1 \le K \le 4$) is the greatest depth a reorder can reach.
• $M$ ($1 \le M \le 5$) is the threshold used by the removal order rule.
• $D$ ($1 \le D \le 10^6$) is the cost of a down shift, which brings the bottom disk of the chosen range to the top.
• $U$ ($1 \le U \le 10^6$) is the cost of an up shift, which sends the top disk of the chosen range to the bottom of that range.
• $R$ ($1 \le R \le 10^6$) is the cost of reversing the chosen range.

Then $2N$ lines follow, each with one label $L$ ($1 \le L \le 20$). The first $N$ of them give the labels of the Master stack from top to bottom, and the remaining $N$ give the labels of your stack from top to bottom.

Print one integer on a single line, the minimum cost of removing every disk from your stack.