### 2011 Canadian Computing Competition, Stage 2

## Day 2, Problem 2: Fixing Disks

You are playing a game with a stack of `N` disks. The goal of the
game is to remove all of the disks from your stack. However, there is a cost
associated with removing disks, and you wish to minimize the cost of removing
all the disks from your stack.

Each disk contains a label `L`, a positive integer.

You are also given a "Master stack" of `N` disks which you can use
to help you remove disks from your stack.

You can remove disks from the top of your stack of disks in two ways:

- remove a disk at the top of your stack: if label of the disk on top of your
stack is
`c`, that disk can be removed from your stack with cost`c`; - remove a disk from both the top of the Master stack and the top of your stack if the label is the same between both disks: in this case, there is no cost with removing both disks.

You are also allowed to modify the order of the top `K` elements of
your stack, so long as immediately after each modification, you remove the top
element of your stack. There are three allowed modifications:

- Reverse: you may reverse the order of the top
`r`(2 ≤`r`≤`K`) disks on your stack. In other words, if the top`r`disks are`d`_{1},`d`_{2}, …,`d`(reading from the top down), then after this operation, the top_{r}`r`disks will be`d`, …,_{r}`d`_{2},`d`_{1}(reading from the top down). The cost of one reverse operation is`R`. - (Cyclic Shift) Up: you can shift up one disk in the range of the top
`u`disks (2 ≤`u`≤`K`). For example, if the top four disks are`d`_{1},`d`_{2},`d`_{3},`d`_{4}(read from the top down), you can perform an up shift in the range of the top three elements to get`d`_{2},`d`_{3},`d`_{1},`d`_{4}or an up shift of the top four elements to get`d`_{2},`d`_{3},`d`_{4},`d`_{1}. The cost of one up shift operation is`U`. - (Cyclic Shift) Down: you can shift down one disk in the range of the top
`d`disks (2 ≤`d`≤`K`). For example, if the top four disks are`d`_{1},`d`_{2},`d`_{3},`d`_{4}(read from the top down), you can perform a down shift in the range of the top three elements to get`d`_{3},`d`_{1},`d`_{2},`d`_{4}or a down shift of the top four elements to get`d`_{4},`d`_{1},`d`_{2},`d`_{3}. The cost of one down shift operation is`D`.

If the operations yield a match between the top of the master stack and the top of your stack, you can pop for free. If not, you must pay the cost of the pop.

There is one additional constraint. At any point in the game, if a disk at
level `j` is being popped (levels start at 0 at the bottom of the
stack), then all elements that were originally at level
`j` + `M` or higher must have already been popped,
where `M` is given.

Minimize the cost required to pop all the elements off of your stack.

### Input Format

The first line will contain 6 space-separated integers, in the following order:

`N`(1 ≤`N`≤ 100), the number of disks in each of the stacks`K`(1 ≤`K`≤ 4), the maximum depth at which operations can be done`M`(1 ≤`M`≤ 5), the threshold before which elements can be removed from our stack`D`(1 ≤`D`≤ 10^{6}), the cost for a shift in which the bottom element of the selected range goes to the top`U`(1 ≤`U`≤ 10^{6}), the cost for an up shift operation (in which the top element of the selected range goes to the bottom)`R`(1 ≤`R`≤ 10^{6}), the cost for reversing the top elements of the selected range

2`N` lines will follow, each containing a number `L`
(1 ≤ `L` ≤ 20). The first `N` lines
will contain the labels of the disks in the Master stack, from top to bottom.
The next `N` lines will contain the labels of the disks in your stack,
from top to bottom.

Note: for 20% of the marks in this question, you may assume that
`K` ≤ 2.

### Output Format

Output the integer (on one line) which is the minimal cost required to remove all disks from your stack.

### Sample Input

7 3 3 4 4 3 5 6 3 5 4 1 2 3 5 6 5 1 4 1

### Sample Output

5

### Explanation

We take 3 to the bottom and shift the two blocks below it up, with cost 4. Then we remove four blocks from each stack, remove a 1 from the playing stack, with cost 1, and remove two blocks from each stack.

All Submissions

Best Solutions

**Point Value:** 40 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Jun 07, 2011

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...