1156번 - 장난감

정문이는 생일을 맞아 D일동안 생일파티를 열기로 하였다. 이에 정문이 친구들은 시간을 내어 정문이 생일파티에 참석하기로 하였다. 그리고 정문이는 이번 생일파티는 친구들과 함께 장난감을 갖고 노는 것으로 시간을 보내기로 계획하였다. 좀 더 구체적으로 i번째 날에는 Ti()개의 장난감을 갖고 놀기로 계획을 세웠다.

장난감 가게에는 장난감 하나를 Tc원에 판다. 정문이는 적당히 장난감을 사서 이 장난감들을 계속 재활용하여 파티를 하려고 했으나, 결벽증이 있는 친구들은 새 장난감이나 살균장에서 소독된 장난감이 아니면 안 갖고 놀겠다고 하는 탓에 어쩔 수 없이 계획을 수정하기로 하였다.

정문이가 이용하는 살균장은 두 곳이다. 한 곳은 밤에 장난감을 맡기면 N1일이 지난 아침에 찾아올 수 있고 비용은 한 개당 C1이 든다. 다른 한 곳은 마찬가지로 N2일이 지난 아침에 찾아올 수 있고 비용은 한 개당 C2가 든다.

문제는 정문이를 도와 적당히 장난감을 사고 적당히 이 장난감을 살균장에 맡기는 방식으로 생일파티를 끝낼 수 있는 최소 비용을 구하는 것이다.

첫 줄에는 정수 D(1 ≤ D ≤ 100,000), N1(1 ≤ N1 ≤ D), N2(1 ≤ N2 ≤ D), C1(1 ≤ C1 ≤ 60), C2(1 ≤ C2 ≤ 60), Tc(1 ≤ Tc ≤ 60)가 공백으로 구분되어 주어진다. 두 번째 줄에는 D+1번째 줄까지 i+1번째 줄에는 i번째 날에 필요한 장난감의 수가 주어진다.

첫 줄에 생일파티를 끝내기 위한 최소비용을 출력한다.

Day 1 - 8개의 장난감을 $24에 구입한다. 이 날 장난감을 모두 갖고 놀고 밤에 2개는 1번 살균장에 6개는 2번 살균장에 맡긴다. Day 2 - 아침에 어제 1번 살균장에 맡겼던 2개를 $4원을 주고 찾아온다. 그리고 갖고 논 후 1개의 장난감을 2번 살균장에 맡긴다. Day 3 - 이틀 전 2번 살균장에 맡겼던 6개의 장난감을 $6를 지불하고 찾아온다. Day 4 - 이틀 전 2번 살균장에 맡겼던 1개의 장난감을 $1을 지불하고 찾아온다. 이로써 총 지불액은 $35가 된다. ※ Test case의 70%는 D가 500 이하이다.