깜짝 선물

준규는 도현이에게 줄 깜짝 선물을 준비했다. 직접 전해 줄 용기가 없어져서, 도현이가 자주 가는 장소들에 선물을 하나씩 놓아 두려고 한다.

모든 장소와 선물을 보관한 창고는 같은 직선 위에 있다. 각 장소의 위치는 창고에서 떨어진 거리로 주어진다.

준규는 트럭으로 선물을 나를 수 있다. 트럭에는 한 번에 최대 A개의 선물을 실을 수 있다. 트럭이 1km 이동할 때마다 B원의 비용이 들며, 이 비용은 트럭에 실린 선물의 개수와 관계없이 같다. 처음에 트럭은 창고에 있다.

선물을 배달하려면 트럭을 주차한 상태여야 한다. 주차할 때마다 C원의 주차비가 들지만, 창고에서 선물을 싣기 위해 멈추는 경우에는 주차비를 내지 않는다. 트럭은 어느 위치에나 주차할 수 있다. 주행 중에 선물을 던져서 배달할 수는 없다.

주차한 곳에서 선물을 들고 걸어서 배달할 수도 있다. 걸어서 이동할 때는 한 번에 선물 하나만 들 수 있다. 선물을 들고 1km 걸을 때마다 D원의 비용이 들고, 빈손으로 걷는 이동에는 비용이 들지 않는다.

선물의 개수, 각 선물을 놓아야 하는 위치, 트럭의 용량 A, 트럭 이동 비용 B, 주차비 C, 도보 이동 비용 D가 주어진다. 모든 선물을 배달하는 데 필요한 최소 비용을 구하라. 모든 선물을 배달한 뒤 트럭은 창고로 돌아오지 않아도 된다.

첫째 줄에 선물을 배달해야 하는 위치의 수 N이 주어진다. (1 <= N <= 50)

둘째 줄에는 각 선물을 배달해야 하는 곳과 창고 사이의 거리가 주어진다. 각 거리는 1 이상 1,000,000 이하의 정수이며, 단위는 km이다.

셋째 줄에는 네 정수 A, B, C, D가 주어진다. (1 <= A <= 50, 0 <= B, C, D <= 1,000,000)

모든 선물을 배달하는 데 필요한 최소 비용을 출력한다.

첫 번째 공개 테스트에서는 선물을 모두 트럭에 싣고 거리 2인 위치까지 이동한 뒤 주차한다. 그곳의 선물을 배달하고, 선물 하나를 들고 거리 1인 위치까지 걸어가 배달한다. 빈손으로 돌아온 뒤 다른 선물을 들고 거리 3인 위치까지 걸어가 배달하면 총 비용은 13이다.