주차 요금 지불

시간 제한2초메모리 제한1024 MB

요약

1일, 7일, 28일 이용권 가격과 방문 일수 n이 주어질 때, n일 전체를 덮는 최소 비용을 구합니다.

문제

로만은 휴가 동안 플랫랜드에서 아파트와 고급 자동차를 빌렸다. 자동차는 마당에 둘 수 없으므로 가장 가까운 경비 주차장에 주차 공간을 빌리려 한다. 숙소와 자동차에 이미 돈을 많이 썼기 때문에, 주차 요금으로 낼 버를을 최대한 줄이고 싶어 한다.

주차장에는 세 가지 요금제가 있다.

로만은 플랫랜드에서 $n$ 일 동안 머무를 계획이다. 각 요금제는 몇 번이든 살 수 있고, 결제한 기간이 필요한 기간보다 길어도 된다. 로만이 $n$ 일 모두 주차장을 사용하려면 최소 몇 버를을 내야 하는가?

첫 줄에 정수 $a$ , $b$ , $c$ ( $1 \le a \le b \le c \le 1000$ )가 주어진다. 각각 첫 번째, 두 번째, 세 번째 요금제를 한 번 살 때의 가격(버를)이다.

둘째 줄에 정수 $n$ ( $1 \le n \le 10^{15}$ )이 주어진다. 로만이 플랫랜드에 머무르며 경비 주차장에 자동차를 세워 둘 날짜 수다.

로만이 낼 최소 버를 수를 정수 하나로 출력한다.

첫 번째 예시에서는 주간권을 2장 사는 것이 유리하다. 가격은 $2 \cdot 7 = 14$ 버를이고, $14$ 일을 덮을 수 있다.

두 번째 예시에서는 주간권 5장과 일일권 1장을 사는 것이 유리하다. 결제된 일수는 정확히 $36$ 일이고, 가격은 $1 \cdot 2 + 5 \cdot 9 + 0 \cdot 38 = 47$ 버를이다.