톱니바퀴 자물쇠

안톤은 컴퓨터 게임을 아주 좋아한다. 얼마 전 Heroes of Keyboard and Mouse라는 새 게임이 나왔고, 그는 바로 구매해서 컴퓨터에 설치했다. 이 게임은 퀘스트 장르라서, 진행하려면 여러 임무(퀘스트)를 차례대로 수행해야 한다.

안톤이 며칠째 붙잡고 있는 퀘스트는 자물쇠를 여는 것이다. 자물쇠는 일렬로 놓인 $n$개의 톱니바퀴로 이루어져 있다. $i$번째 톱니바퀴에는 $s_i$개의 톱니가 있고, 각 톱니에는 0부터 $s_i - 1$까지의 수가 적혀 있다. 1번 톱니바퀴는 2번과만 맞물려 있고, 2번은 1번과 3번에 맞물려 있다. 3번은 2번과 4번에 맞물려 있으며, 이런 식으로 이어진다. $(n-1)$번은 $(n-2)$번과 $n$번에 맞물려 있고, $n$번은 $(n-1)$번과만 맞물려 있다.

자물쇠에는 $n$개의 창과 $n$개의 손잡이가 있다. $i$번째 창으로는 $i$번째 톱니바퀴의 톱니 중 하나에 적힌 수를 볼 수 있고, $i$번째 손잡이로는 $i$번째 톱니바퀴를 돌린다. $i$번째 톱니바퀴를 시계 방향으로 한 칸 돌리기 전에 $i$번째 창에 $x$가 보였다면, 돌린 뒤에는 $(x+1) \bmod s_i$가 보인다. 반시계 방향으로 한 칸 돌리면 $x$ 대신 $(x-1+s_i) \bmod s_i$가 보인다. 톱니바퀴를 시계 방향으로 돌리면 맞물린 톱니바퀴는 반시계 방향으로 돌고, 반대로 반시계 방향으로 돌리면 맞물린 톱니바퀴는 시계 방향으로 돈다. 그림 1은 1번 톱니바퀴를 시계 방향으로 돌리기 전과 후의 모습이다. 굵은 선은 창에 보이는 수가 적힌 톱니를 나타낸다.

그림 1. 톱니바퀴의 회전

처음에 $i$번째 창에는 $a_i$가 보인다. 자물쇠를 열려면 모든 $i$번째 창에 $b_i$가 보이도록 만들어야 한다.

$i$번째 손잡이로 $i$번째 톱니바퀴를 돌릴 수 있다. 톱니바퀴를 돌리면 그와 직접 또는 다른 톱니바퀴를 거쳐 연결된 모든 톱니바퀴도 함께 움직인다. 톱니바퀴를 한 칸 돌리는 데 1초가 걸린다. 또한 $i$번째 창에 $b_i$가 보이는 상태라면, 손잡이를 눌러 톱니바퀴를 눌러 넣을 수 있다. 그러면 $i$번째 톱니바퀴는 $(i-1)$번째 및 $(i+1)$번째 톱니바퀴(존재하는 경우)와 더 이상 맞물리지 않는다. 눌러 넣은 톱니바퀴는 그 상태 그대로 영원히 남는다. 손잡이를 눌러 톱니바퀴를 눌러 넣는 데 $k$초가 걸린다.

그림 2의 왼쪽은 2번 톱니바퀴를 눌러 넣기 전 상태이고, 오른쪽은 1번을 시계 방향, 3번을 반시계 방향으로 돌린 뒤 2번을 눌러 넣은 상태이다. 2번을 눌러 넣은 뒤에는 1번과 3번이 서로 독립적으로 돈다는 점에 유의한다.

그림 2. 톱니바퀴 눌러 넣기

안톤은 퀘스트를 끝내기 위해 자물쇠를 최대한 빨리 열어야 한다. 톱니바퀴의 정보, 시작 상태, 목표 상태가 주어졌을 때, 안톤이 자물쇠를 열 수 있는 최소 시간을 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 25$, $1 \le k \le 100$). 둘째 줄에는 톱니바퀴의 크기 $s_1, s_2, \ldots, s_n$이 주어진다. 모든 $s_i$는 3 이상 10 이하의 정수이다.

셋째 줄에는 톱니바퀴의 시작 위치 $a_1, a_2, \ldots, a_n$이, 넷째 줄에는 목표 위치 $b_1, b_2, \ldots, b_n$이 주어진다. 모든 $i$에 대해 $0 \le a_i < s_i$이고 $0 \le b_i < s_i$이다.

자물쇠를 여는 데 필요한 최소 시간을 출력한다.