1776번 - 깜짝 선물

준규는 삐져버린 도현이를 위해 깜짝 선물을 준비하려고 한다. 도현이는 준규의 문자를 계속해서 답장하지 않았고, 준규는 점점 직접 선물을 줄 용기가 없어졌다. 따라서, 도현이가 자주 가는 장소에 선물을 맡겨놓으려고 한다.

도현이가 자주 가는 곳은 모두 일직선 상에 있다. 또, 준규가 선물을 보관해놓은 창고도 일직선상에 있다.

준규는 트럭을 이용해 선물을 배달한다. 준규의 트럭에는 최대 A개의 물건까지 넣을 수 있다. 또, 트럭을 타고 1km를 이동할 때마다, 트럭은 B원을 소비하게 된다. 트럭에 몇 개의 물건이 실려있는지와 상관 없이 항상 1km를 이동할 때마다 B원을 소비한다. 가장 처음에 트럭은 선물을 보관해놓은 창고에 있다.

어떤 곳에 선물을 전달할 때는, 트럭을 주차시켜야 한다. 이때, 주차비는 C원이다. 단, 창고에서 물건을 실을 때는, 주차비를 내지 않아도 된다. 트럭은 어느 곳에서나 주차를 할 수 있다. 준규가 선물을 배달할 때는 반드시 주차를 해야 한다. 즉, 트럭을 운전하면서 선물을 던져서 배달할 수 없다.

선물을 걸어서 배달할 수도 있다. 이때는, 한 개씩만 배달할 수 있다. 선물을 들고 걸어갈 때 드는 비용은 D원이다. 선물을 들지 않고 걸어갈 때는 비용이 들지 않는다.

선물의 개수와 놓여야하는 위치, 트럭이 실을 수 있는 선물의 최대 개수 A, 트럭을 타고 1km를 이동할 때마다 드는 비용 B, 주차비 C, 걸어갈 때 드는 비용 D가 주어졌을 때, 모든 선물을 배달하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 선물을 모두 배달하고 난 이후에 트럭은 원래 창고에 돌아가지 않아도 된다.

첫째 줄에 선물을 배달해야 하는 위치의 수 N(1 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 선물을 배달해야 하는 곳과 창고 사이의 거리가 주어진다. 거리는 1,000,000보다 작거나 같은 자연수이고, km 단위이다. 셋째 줄에는 네 정수 A, B, C, D가 주어진다. (1 ≤ A ≤ 50, 0 ≤ B, C, D ≤ 1,000,000)

배달하는 비용의 최솟값을 출력한다.

모든 선물을 일단 트럭에 실고 2로 간다.(2*2) 주차를 한 후에(3), 2에 선물을 배달하고, 선물을 한 개 들고 1의 위치로 가서 배달한다.(3*1) 다시 2로 돌아온 후에 (선물을 들고 있지 않을 때는, 비용이 들지 않으므로) 트럭에서 선물을 하나 들고 3의 위치로 배달한다.(3*1) 따라서 답은 2*2+3+3+3 = 13이 된다.