원반 정리하기

원반 $N$개가 쌓인 더미로 게임을 한다. 목표는 내 더미에서 원반을 모두 없애는 것이다. 원반을 없앨 때마다 비용이 들기 때문에, 전체 비용을 가장 작게 만들어야 한다.

원반마다 번호 $L$이 하나씩 적혀 있고, $1 \le L \le 20$이다.

내 더미를 비우는 데 쓰라고 원반 $N$개짜리 마스터 더미도 함께 주어진다.

내 더미의 맨 위 원반을 없애는 방법은 두 가지다.

내 더미의 맨 위 원반만 없앤다. 그 원반의 번호가 $c$면 비용은 $c$다.
마스터 더미의 맨 위 원반과 내 더미의 맨 위 원반을 함께 없앤다. 두 번호가 같을 때만 쓸 수 있고, 비용은 들지 않는다.

내 더미의 위쪽 $K$개까지는 순서를 바꿀 수 있다. 단, 순서를 한 번 바꾸면 곧바로 맨 위 원반을 없애야 하므로, 원반 하나를 없앨 때 순서 바꾸기는 많아야 한 번이다. 순서 바꾸기는 위쪽 몇 개를 구간으로 잡아 적용하며, 구간 크기는 더미에 남은 원반 수를 넘을 수 없다. 쓸 수 있는 방법은 세 가지다.

뒤집기. 위쪽 $r$개($2 \le r \le K$)의 순서를 뒤집는다. 위에서부터 읽은 원반이 $d_1, d_2, \ldots, d_r$이면 뒤집은 뒤에는 위에서부터 $d_r, \ldots, d_2, d_1$이 된다. 한 번 뒤집는 비용은 $R$이다.
위로 돌리기. 위쪽 $u$개($2 \le u \le K$) 안에서 한 칸 위로 돌린다. 위에서부터 읽은 위쪽 네 개가 $d_1, d_2, d_3, d_4$일 때 위쪽 세 개를 위로 돌리면 $d_2, d_3, d_1, d_4$가 되고, 네 개를 모두 위로 돌리면 $d_2, d_3, d_4, d_1$이 된다. 한 번 돌리는 비용은 $U$다.
아래로 돌리기. 위쪽 $d$개($2 \le d \le K$) 안에서 한 칸 아래로 돌린다. 위에서부터 읽은 위쪽 네 개가 $d_1, d_2, d_3, d_4$일 때 위쪽 세 개를 아래로 돌리면 $d_3, d_1, d_2, d_4$가 되고, 네 개를 모두 아래로 돌리면 $d_4, d_1, d_2, d_3$이 된다. 한 번 돌리는 비용은 $D$다.

순서를 바꾼 뒤 마스터 더미의 맨 위와 내 더미의 맨 위 번호가 같으면 두 원반을 공짜로 없앨 수 있다. 이때도 1번 방법은 그대로 쓸 수 있어서, 번호만큼 비용을 내고 내 더미의 원반만 없애도 된다. 번호가 다르면 1번 방법만 남는다.

없애는 순서에는 제약이 하나 더 있다. 내 더미의 층은 맨 아래를 $0$층으로 하여 센다. 처음에 $j$층에 있던 원반을 없애려면, 처음에 $j + M$층 이상에 있던 원반이 이미 모두 없어져 있어야 한다.

내 더미를 모두 비우는 데 드는 최소 비용을 구하라.

첫째 줄에 정수 여섯 개 $N$, $K$, $M$, $D$, $U$, $R$가 공백으로 구분되어 주어진다.

$N$ ($1 \le N \le 100$): 각 더미에 쌓인 원반의 수
$K$ ($1 \le K \le 4$): 순서 바꾸기가 닿을 수 있는 가장 깊은 위치
$M$ ($1 \le M \le 5$): 없애는 순서 제약에 쓰는 기준값
$D$ ($1 \le D \le 10^6$): 아래로 돌리기의 비용. 고른 구간의 맨 아래 원반이 맨 위로 온다
$U$ ($1 \le U \le 10^6$): 위로 돌리기의 비용. 고른 구간의 맨 위 원반이 그 구간의 맨 아래로 간다
$R$ ($1 \le R \le 10^6$): 고른 구간을 뒤집는 비용

다음 $2N$개 줄에는 번호 $L$ ($1 \le L \le 20$)이 한 줄에 하나씩 주어진다. 앞의 $N$개 줄은 마스터 더미의 번호를 위에서 아래 순서로, 뒤의 $N$개 줄은 내 더미의 번호를 위에서 아래 순서로 나타낸다.

원반 정리하기

문제

입력

출력