408924: GYM103382 2 Пирожки

Рядом с домом Пети расположена пекарня, в которой пекут вкусные пирожки с ягодами. Пете очень нравятся три вида пирожков: с брусникой, с черникой и с вишней. Пирожок с брусникой стоит $$$A$$$ рублей, пирожок с черникой стоит $$$B$$$ рублей, пирожок с вишней стоит $$$C$$$ рублей.

Каждый день, проходя мимо пекарни, Петя покупает пирожок одного из этих трёх видов. При этом он соблюдает следующие правила:

• если в некоторый день он купил пирожок с брусникой, то на следующий день он купит пирожок с черникой;
• если в некоторый день он купил пирожок с черникой, то на следующий день он купит пирожок с вишней;
• если в некоторый день он купил пирожок с вишней, то на следующий день он купит пирожок с брусникой.

Например, если сегодня Петя купит пирожок с брусникой, то завтра он купит пирожок с черникой, послезавтра — пирожок с вишней, на следующий за послезавтра день — пирожок с брусникой, и так далее.

Зная, какой пирожок Петя купит сегодня, определите, сколько денег Петя потратит на пирожки в течение $$$N$$$ дней, начиная с сегодняшнего.

В первой строке входных данных содержится целое число $$$A$$$ $$$\left(1 \le A \le 10^6 \right)$$$ — цена пирожка с брусникой.

Во второй строке содержится целое число $$$B$$$ $$$\left(1 \le B \le 10^6 \right)$$$ — цена пирожка с черникой.

В третьей строке содержится целое число $$$C$$$ $$$\left(1 \le C \le 10^6\right)$$$ — цена пирожка с вишней.

В четвёртой строке содержится целое число $$$N$$$ $$$\left(1 \le N \le 2 \cdot 10^9 \right)$$$ — количество дней, за которые нужно посчитать расходы Пети на пирожки.

В пятой строке содержится число $$$1$$$, $$$2$$$ или $$$3$$$, указывающее, какой пирожок Петя купит сегодня. Число $$$1$$$ соответствует пирожку с брусникой, число $$$2$$$ — пирожку с черникой, число $$$3$$$ — пирожку с вишней.

Выведите единственное целое число — сумму, которую Петя потратит на пирожки.

Обратите внимание, что для больших значений $$$N$$$ ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#)

Решение, правильно работающее только для случаев, когда $$$N \le 3$$$, будет оцениваться в $$$9$$$ баллов.

Решение, правильно работающее только для случаев, когда $$$N \le 1000$$$, будет оцениваться в $$$72$$$ балла.

14
12
11
7
1

88

14
12
11
7
2

86

14
12
11
7
3

85

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

В первом примере первой покупкой Пети будет пирожок с брусникой. Значит, покупки Пети за семь дней могут быть описаны последовательностью брусника, черника, вишня, брусника, черника, вишня, брусника. Сумма, потраченная на покупки, составит $$$14 + 12 + 11 + 14 + 12 + 11 + 14 = 88$$$ рублей.

Во втором примере первой покупкой Пети будет пирожок с черникой. Соответственно, покупки Пети за семь дней могут быть описаны последовательностью черника, вишня, брусника, черника, вишня, брусника, черника. Сумма, потраченная на покупки, составит $$$12 + 11 + 14 + 12 + 11 + 14 + 12 = 86$$$ рублей.

В третьем примере первой покупкой Пети будет пирожок с вишней. Следовательно, покупки Пети за семь дней могут быть описаны последовательностью вишня, брусника, черника, вишня, брусника, черника, вишня. Сумма, потраченная на покупки, составит $$$11 + 14 + 12 + 11 + 14 + 12 + 11 = 85$$$ рублей.