Задача . C. Газопровод

Вам назначили задачу проложить газопровод вдоль дороги. Для простоты будем считать, что дорога — это отрезок \([0, n]\) на оси \(OX\). На дороге может быть несколько перекрестков, но для простоты будем считать каждый перекресток как интервал \((x, x + 1)\) для некоторого целого \(x\). Таким образом, можно представить дорогу как двоичную строку, состоящую из \(n\) символов, где цифра 0 означает, что текущий интервал не содержит перекресток, а 1 означает, что интервал содержит перекресток.

Обычно газопровод можно установить вдоль дороги на высоте \(1\) вместе с поддерживающими его столбами в каждой целой точке (поэтому при установке вдоль дороги \([0, n]\) нам необходимо поставить \(n + 1\) столб). Но на перекрестках нам необходимо поднять трубу на высоту \(2\), чтобы она не мешала проезду машин.

Мы можем поднять или опустить трубу за счет вставки зигзагообразных частей. Каждый зигзаг можно представить как отрезок \([x, x + 1]\) с целым \(x\), состоящий из трех частей: \(0.5\) единицы горизонтальной трубы + \(1\) единицы вертикальной трубы + \(0.5\) горизонтальной. Заметьте, что если труба находится на высоте \(2\), столбы, ее поддерживающие, также должны быть длины \(2\).

Каждая единица длины газопровода стоит нам \(a\) бурлей, а каждая единица длины столба — \(b\) бурлей. Поэтому не всегда выгодно просто пустить трубопровод на высоте \(2\). Определите форму трубопровода с минимальной возможной ценой, а также его цену.

Заметим, что вы обязаны начать и закончить трубу на высоте \(1\), а также гарантируется, что первый и последний символы во входной строке обязательно равны 0.