Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, …, \(n\). Получились числа 1, 10, 11, 100, 101, 110, 111, …

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число \(k\) и в каждой строке, идя слева направо, выделил красным цветом каждый \(k\)-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, \(k\) + 1, 2\(k\) + 1, … Например если \(k\) = 2, \(n\) = 56 то получились бы такие строки:

(красные нули выделены жирным шрифтом и подчеркнуты)

Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.

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

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

Изначально замок находится в состоянии, в котором в \(i\)-ое окошко видно число \(a_i\). Для того, чтобы его открыть, необходимо перевести его в состояние, в котором в \(i\)-ое окошко видно число \(b_i\).

С помощью \(i\)-ой ручки можно поворачивать \(i\)-ую шестеренку. Разумеется, если повернуть \(i\)-ую шестеренку, то придут в движение и все шестеренки, с которыми она соединена - напрямую или через другие шестеренки. Поворот любой шестеренки на одно деление занимает одну секунду. Кроме этого, если \(i\)-ая шестеренка находится в таком состоянии, что в \(i\)-ое окошко видно число \(b_i\) (то есть, она находится в положении, соответствующем требуемому состоянию замка), то ее можно вдавить, нажав на ее ручку. В результате этого \(i\)-ая шестеренка перестает быть соединенной с \((i-1)\)-ой и \((i+1)\)-ой (если, конечно, они существуют). Вдавленная шестеренка остается в таком состоянии навсегда. На то, чтобы нажать на ручку и вдавить шестеренку требуется \(k\) секунд. На рис. 2 слева показано положение шестеренок до вдавливания второй из них, а справа - после вдавливания и после поворота первой по часовой стрелке, а третьей - против. Отметим, что после вдавливания второй шестеренки первая и третья вращаются независимо друг от друга.

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