Optimal Napkin Usage Plan

A restaurant operates over a sequence of \(N\) days. On day \(i\) the restaurant requires \(r_i\) napkins. To supply the daily demand, the restaurant can either:

• Purchase new napkins at a cost of \(p\) cents each (available immediately).
• Send used (dirty) napkins for fast washing at a cost of \(f\) cents per napkin. The fast wash takes \(m\) days so that a napkin used on day \(i\) becomes available on day \(i+m\).
• Send used napkins for slow washing at a cost of \(s\) cents per napkin. The slow wash takes \(n\) days (with \(n > m\)) so that a napkin used on day \(i\) becomes available on day \(i+n\). Note that \(s < f\) (i.e. slow washing is cheaper but takes longer).

At the end of each day, the restaurant must decide how many dirty napkins to send immediately to fast wash, how many to slow wash, and how many to postpone washing for later decision. However, the total number of new napkins purchased plus the napkins that have just been cleaned must exactly meet the demand on that day.

The objective is to plan the usage over the \(N\) days so that the total cost is minimized. In other words, you must choose an optimal napkin “chain” for each unit used. A chain may start with a purchase on a day and can later be extended by cleaning (via fast or slow wash) to cover another day’s demand. If a chain extends from day \(i\) to day \(j\) (with \(j=i+m\) or \(j=i+n\)), an additional cost of \(f\) or \(s\) is incurred respectively. Each napkin may be reused at most once per day, and a reuse decision (i.e. washing) helps cover a future day’s requirement.

Input and Output Hint: This problem can be modeled as a minimum cost flow problem over a directed acyclic graph. Create nodes for days \(1\) to \(N\) with the following edges:

• An edge from a super‐source to day \(i\) with cost \(p\) (representing buying a new napkin for that day) and capacity at least \(r_i\).
• An edge from day \(i\) to day \(i+m\) (if \(i+m \le N\)) with cost \(f\) (fast wash) and large capacity.
• An edge from day \(i\) to day \(i+n\) (if \(i+n \le N\)) with cost \(s\) (slow wash) and large capacity.
• An edge from each day \(i\) to a super‐sink (to “consume” a napkin usage) with zero cost.

The minimum cost flow that sends a total of \(\sum_{i=1}^N r_i\) units from the source to the sink gives the minimum total cost.

Your task is to compute this minimum cost.

inputFormat

The first line contains six integers: N, p, m, n, f, s.
The second line contains N integers: r₁ r₂ ... r_N, where r_i is the demand on day i.

outputFormat

Output a single integer which is the minimum total cost to cover the demands over N days.

sample

3 10 1 2 7 5
1 1 1

25