Napkin Plan

Problem Source

Network Flow 24 Problems

Problem Description

A restaurant needs a different number of napkins on each of $n$ consecutive days. Suppose day $i$ needs $r_i$ napkins.

Each day the restaurant may do the following:

• Buy new napkins, at a cost of $c_0$ per napkin.
• Send dirty napkins to the fast laundry, which takes $d_1$ days and costs $c_1$ per napkin.
• Send dirty napkins to the slow laundry, which takes $d_2$ days and costs $c_2$ per napkin.

At the end of each day, the restaurant must decide how many dirty napkins to send to the fast laundry, how many to the slow laundry, and how many to keep for deferred washing. However, the number of clean napkins obtained from laundering plus the number of newly bought napkins each day must meet that day's demand.

Design an algorithm to arrange the napkin usage plan for the $n$ days reasonably, so as to minimize the total cost.

Input Format

The first line contains six positive integers $n, c_0, d_1, c_1, d_2, c_2 (1\leq n \leq 800, 1\leq c_i\leq 100)$.

The following $n$ lines each contain one integer $r_1, r_2, \dots, r_n (1\leq r_i\leq 1000)$.

Output Format

Output the minimum total cost for the restaurant to use napkins over the $n$ consecutive days.

Sample Input

3 11 2 2 3 1
1
7
5

Sample Output

134

Constraints

$1\leq n \leq 800$, $1\leq c_i\leq 100$, $1\leq r_i\leq 1000$.

Hint

• This is a classic minimum-cost maximum-flow problem: model each day with a "demand" node (needs $r_i$ clean napkins) and a "dirty" node (receives used napkins), then connect buying, fast laundering, and slow laundering as edges with the appropriate costs and delays.