시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 145 | 24 | 17 | 27.419% |
정문이는 생일을 맞아 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번째 날에 필요한 장난감의 수가 주어진다.
첫 줄에 생일파티를 끝내기 위한 최소비용을 출력한다.
4 1 2 2 1 3 8 2 1 6
35
※ Test case의 70%는 D가 500 이하이다.