Description

A restaurant requires a varying number of napkins over $n$ consecutive days. Suppose on day $i$ ($i = 1, 2, \ldots, n$) it needs $r_i$ napkins. The restaurant can purchase new napkins at any time, at a cost of $p$ per napkin. Used napkins must be washed before reuse. Sending one used napkin to laundry A returns it after $m_1$ days at a cost of $c_1$; sending one used napkin to laundry B returns it after $m_2$ days at a cost of $c_2$. For example, a napkin used on day $k$ and sent to laundry A can be used on day $k+m_1$.

Arrange the napkin usage plan over $n$ days to minimize the total cost.

Input Format

The first line contains six positive integers $n, m_1, m_2, c_1, c_2, p$.

The next $n$ lines each contain a positive integer $r_i$.

Output Format

Output one line containing a single positive integer, the minimum total cost.

4 1 2 2 1 3
8
2
1
6

35

Hint

【Sample Explanation】

Day 1: Buy 8 napkins, costing 24. Send 2 napkins to laundry A and 6 napkins to laundry B.

Day 2: Take back 2 napkins from laundry A, costing 4. Send 1 napkin to laundry B.

Day 3: Take back 6 napkins from laundry B, costing 6.

Day 4: Take back 1 napkin from laundry B, costing 1. This achieves the minimum cost.

【Constraints】

For 30% of the testdata, $1 \leq n \leq 5$, $1 \leq c_1, c_2, p \leq 5$, $1 \leq r_i \leq 5$.

For 50% of the testdata, $1 \leq n \leq 100$, $1 \leq r_i \leq 50$.

For 70% of the testdata, $1 \leq n \leq 5000$.

For 100% of the testdata, $1 \leq n \leq 200000$, $1 \leq m_1, m_2 \leq n$, $1 \leq c_1, c_2, p \leq 100$, $1 \leq r_i \leq 100$.

Translated by ChatGPT 5