Предположим, вы стоите на плоскости \(XY\) в точке \((0, 0)\) и хотите попасть в точку \((n, n)\).
Вы можете двигать только в двух направлениях:
- вправо, т. е. горизонтально и в направлении увеличения \(x\) коодинаты,
- или вверх, т. е. вертикально и в направлении увеличения \(y\) координаты.
Другими словами, ваш путь имеет следующую структуру:
- первоначально, вы выбираете: пойти вправо или вверх;
- далее вы проходите некоторое положительное целое расстояние в выбранном направлении (расстояния можно выбирать независимо);
- далее вы меняете направление движения (от «вправо» к «вверх», либо от «вверх» к «вправо») и повторяете процесс.
Вам не нравится менять свое направление слишком много раз, а потому вы сделаете не более \(n - 1\) изменений направления.
В результате ваш путь будет представлять ломаную от \((0, 0)\) к \((n, n)\), состоящую из не более чем \(n\) отрезков, каждый из которых имеет положительную целую длину, а также вертикальные и горизонтальные отрезки идут по очереди.
Не все пути равны. У вас есть \(n\) целых чисел \(c_1, c_2, \dots, c_n\), где \(c_i\) — это цена \(i\)-го отрезка.
Используя эти цены, можно определить цену пути как сумму длин отрезков этого пути умноженных на их стоимости, т. е. если путь состоит из \(k\) отрезков (\(k \le n\)), то цена пути равна \(\sum\limits_{i=1}^{k}{c_i \cdot length_i}\) (отрезки нумеруются от \(1\) по \(k\) в порядке их обхода).
Определите путь минимальной стоимости и выведите его цену.
Выходные данные
Для каждого набора входных данных вы должны вывести минимальную цену пути из \((0, 0)\) в \((n, n)\), состоящего из не более \(n\) чередующихся отрезков.
Примечание
В первом примере из условия, чтобы достигнуть \((2, 2)\), нужно сделать хотя бы один поворот, и путь может состоять из \(2\) отрезков: горизонтального длины \(2\) и вертикального длины \(2\). Стоимость равна \(2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202\).
Во втором примере можно построить путь из \(3\) отрезков: длины \(1\), длины \(3\) и длины \(2\). Стоимость равна \(1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13\).
В третьем примере можно построить путь из \(4\) отрезков: длины \(1\), длины \(1\), длины \(4\) и длины \(4\). Стоимость равна \(1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19\).