21415번 - Замóк с шестеренками 다국어

Антон --- большой любитель компьютерных игр. Совсем недавно вышла новая игра Heroes of Keyboard and Mouse, и он, конечно же, сразу ее купил и установил на свой компьютер. Эта игра относится к жанру квестов, и поэтому ее прохождение сводится к последовательному выполнению ряда заданий (квестов).

Один из квестов, над которым Антон бьется уже не первый день состоит в том, что требуется открыть замок. Замок состоит из $n$ шестеренок, стоящих в ряд, --- $i$-ая из шестеренок имеет $s_i$ зубцов, на каждом из которых написано число от $0$ до $s_i - 1$. Первая шестеренка зацеплена только со второй, вторая зацеплена с первой и третьей, третья --- со второй и четвертой, $\ldots$, $(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$-ую шестеренку. Разумеется, если повернуть $i$-ую шестеренку, то придут в движение и все шестеренки, с которыми она соединена --- напрямую или через другие шестеренки. Поворот любой шестеренки на одно деление занимает одну секунду. Кроме этого, если $i$-ая шестеренка находится в таком состоянии, что в $i$-ое окошко видно число $b_i$ (то есть, она находится в положении, соответствующем требуемому состоянию замка), то ее можно вдавить, нажав на ее ручку. В результате этого $i$-ая шестеренка перестает быть соединенной с $(i-1)$-ой и $(i+1)$-ой (если, конечно, они существуют). Вдавленная шестеренка остается в таком состоянии навсегда. На то, чтобы нажать на ручку и вдавить шестеренку требуется $k$ секунд. На рис. 2 слева показано положение шестеренок до вдавливания второй из них, а справа --- после вдавливания и после поворота первой по часовой стрелке, а третьей --- против. Отметим, что после вдавливания второй шестеренки первая и третья вращаются независимо друг от друга.

Рис. 2. Вдавливание шестеренки

Для того, чтобы выполнить квест, Антону необходимо открыть замок как можно быстрее. Напишите программу, которая по описанию замка, его начального состояния и требуемого состояния, вычислит минимальное время, за которое Антон может открыть замок.

Первая строка входного файла содержит два целых числа: $n$ и $k$ ($1 \le n \le 25$, $1 \le k \le 100$). Вторая строка входного файла содержит $n$ чисел: $s_1$, $s_2$, $\ldots$, $s_n$ --- размеры шестеренок. Все $s_i$ --- целые числа от 3 до 10.

Третья строка входного файла содержит $n$ целых чисел $a_1$, $a_2$, $\ldots$, $a_n$ --- начальные положения шестеренок (для всех $a_i$ выполняются неравенства $0 \le a_i < s_i$). Четвертая строка входного файла содержит $n$ целых чисел $b_1$, $b_2$, $\ldots$, $b_n$ --- требуемые положения шестеренок (для всех $b_i$ выполняются неравенства $0 \le b_i < s_i$).

В выходной файл выведите минимальное количество времени, которое необходимо для того, чтобы открыть замок.