Minimizing Napkin Usage Cost

A restaurant needs to cover its daily napkin requirement over n consecutive days. On day \(i\) (\(1 \le i \le n\)), it needs \(r_i\) napkins. There are two ways to obtain a napkin for use on a given day:

• New Purchase: A new napkin can be bought anytime at a cost of \(p\) each.
• Recycling (Washing): A used napkin can be sent for washing and then reused after a waiting period. There are two washing shops:
  • Shop A: If a napkin used on day \(k\) is sent to Shop A, it becomes available on day \(k + m_1\) at a cost of \(c_1\) per napkin.
  • Shop B: If a napkin used on day \(k\) is sent to Shop B, it becomes available on day \(k + m_2\) at a cost of \(c_2\) per napkin.
  For example, a napkin used on day \(k\) and washed at Shop A will be ready on day \(k + m_1\).

Every napkin, once used on a day, can either be discarded or sent for washing (via one of the two shops) to be reused in a future day. Each napkin can be used only once per day. The objective is to plan the napkin usage over n days such that the total cost is minimized.

Hint: Think of each napkin as a chain. The cost of a chain that supplies a napkin on a certain day can either be started fresh (buying new) for cost \(p\), or extended from a previous day usage via one of the washing options. For day \(i\), if a chain was used on day \(i-m_1\), it can be extended with an additional cost \(c_1\), and similarly for day \(i-m_2\) with cost \(c_2\). Formally, for day \(i\) the minimal cost to obtain a napkin is:

\( F(i) = \min\bigl\{ p,\; [i - m_1 \ge 1] \; F(i - m_1) + c_1,\; [i - m_2 \ge 1] \; F(i - m_2) + c_2 \bigr\} \)

The answer is given by \( \sum_{i=1}^{n} r_i \times F(i) \).

inputFormat

The first line contains six integers: n p m1 c1 m2 c2 where:

• \(n\): the number of days.
• \(p\): cost to buy a new napkin.
• \(m_1\): waiting days for Shop A.
• \(c_1\): washing cost at Shop A.
• \(m_2\): waiting days for Shop B.
• \(c_2\): washing cost at Shop B.

The second line contains \(n\) non-negative integers r1 r2 ... rn, representing the napkin requirement for each day.

outputFormat

Output a single integer, the minimal total cost to cover the napkin usage for all n days.

sample

5 10 2 3 3 1
1 2 3 4 5

150