34510번 - 초콜릿 우유가 좋아

문제

피자는 우유가 좋다. 그중에서도 초콜릿 우유를 가장 좋아한다. 초콜릿 우유를 너무 좋아한 나머지, 피자는 초콜릿 우유갑을 이용해 우유탑을 쌓아 올리려고 한다.

우유갑은 위에서부터 꼭지, 머리, 몸통의 세 부분으로 이루어져 있다. 우유갑의 모습을 옆에서 본 그림을 기준으로 위에서부터 차례대로 선분, 이등변삼각형, 직사각형의 모양을 하고 있고 각 부분의 높이는 각각 $H_1,ドル $H_2,ドル $H_3$이다. $(H_1 \le H_2 \le H_3)$

피자는 우유갑을 여러 개 쌓아 $N$층 우유탑을 만들려고 한다. 우유탑을 쌓는 과정은 다음과 같다. 정방향은 우유갑의 꼭지가 위로 향하는 방향으로 배치되는 것을, 역방향은 우유갑의 꼭지가 아래로 향하는 방향으로 배치되는 것을 뜻한다.

• 1ドル$층은 우유갑을 원하는 개수만큼 정방향이 되도록 일렬로 바닥 위에 세운다.
• $k \ge 1$에 대해, $k$층까지 쌓여 있을 때 $k+1$층을 올리는 방법은 다음 두 경우뿐이다.
  • $k$층의 우유갑이 정방향이면, $k+1$층의 우유갑은 역방향으로 올린다. 이때 역방향 우유갑의 머리는 아래층의 우유갑의 머리와 완전히 맞닿아야 하고 꼭지는 바로 아래층의 두 몸통 사이 틈으로 들어가게 한다. 이 과정에서 아래층보다 우유갑의 개수가 하나 적어진다.
  • $k$층의 우유갑이 역방향이면, $k+1$층의 우유갑은 바로 위에 정방향으로 올린다.

우유탑을 쌓을 때, 1ドル$층에 공간이 부족하여 우유갑을 놓지 못해 $N$층 우유탑을 만들지 못하는 경우는 존재하지 않는다.

위 그림은 각각 우유갑을 가장 적게 이용하여 1ドル$층부터 4ドル$층까지의 우유탑을 쌓은 예시이다. 왼쪽 우유탑을 도식화하여 오른쪽 그림으로 나타낼 수 있다.

$N$층 우유탑의 전체 높이를 구해보자.

입력

첫 번째 줄에 정수 $H_1,ドル $H_2,ドル $H_3$가 공백으로 구분되어 주어진다.

두 번째 줄에 정수 $N$이 주어진다.

출력

첫 번째 줄에 $N$층 우유탑의 전체 높이를 출력한다.

제한

• 1ドル \le H_1 \le H_2 \le H_3 \le 100$
• 1ドル \le N \le 10^{12}$

힌트