장난감

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

요약
D일 동안 매일 필요한 장난감 수를 맞추기 위해 서로 다른 대기일과 비용을 가진 두 소독 시설과 신규 구매 중 무엇을 택할지 정해 총 비용을 최소화하는 문제입니다.
난이도

어려움10점 중 8점

유형
그리디, 그래프, 동적 계획법, 구간
정답자
아직 제출이 없습니다

문제

정문이는 생일을 맞아 DD일 동안 생일파티를 열기로 했다. 친구들은 파티에 참석하고, 정문이는 매일 장난감을 가지고 놀 계획이다. ii번째 날에는 정확히 TiT_i개의 장난감이 필요하다.

장난감 가게에서는 장난감 하나를 TcT_c원에 판다. 한 번 사용한 장난감은 그냥 다시 사용할 수 없으며, 새 장난감이거나 살균장에서 소독을 마친 장난감만 사용할 수 있다.

정문이가 이용할 수 있는 살균장은 두 곳이다. 첫 번째 살균장은 밤에 장난감을 맡기면 N1N_1일이 지난 아침에 찾아올 수 있고, 비용은 장난감 하나당 C1C_1원이다. 두 번째 살균장은 밤에 맡기면 N2N_2일이 지난 아침에 찾아올 수 있고, 비용은 장난감 하나당 C2C_2원이다.

정문이는 필요한 만큼 장난감을 사고, 사용한 장난감을 적절히 살균장에 맡겨 모든 파티 일정을 마치려고 한다. 파티를 모두 끝내기 위해 필요한 최소 비용을 구하라.

입력

첫째 줄에 정수 DD, N1N_1, N2N_2, C1C_1, C2C_2, TcT_c가 공백으로 구분되어 주어진다.

다음 DD개의 줄 중 ii번째 줄에는 ii번째 날에 필요한 장난감의 수 TiT_i가 주어진다.

출력

생일파티를 모두 끝내기 위한 최소 비용을 출력한다.

제한

  • 1≤D≤100 0001 \le D \le 100\,000
  • 1≤N1,N2≤D1 \le N_1, N_2 \le D
  • 1≤C1,C2≤601 \le C_1, C_2 \le 60
  • 1≤Tc≤601 \le T_c \le 60

예제1

  1. 예제 1

    입력
    4 1 2 2 1 3
8
2
1
6
    예상 출력
    35