[BJWC2018] 餐巾计划问题

题目背景

**本题和网络流24题中的餐巾计划不为重题**

题目描述

一个餐厅在相继的 $n$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天 $(i=1, 2, ..., n)$ 需要 $r_i$ 块餐巾。餐厅可以在任意时刻购买新的餐巾,每块餐巾的费用为 $p$ 。使用过的旧餐巾,则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A,需要等待 $m_1$ 天后才能拿到新餐巾,其费用为 $c_1$ ;把一块旧餐巾送到清洗店B,需要等待 $m_2$ 天后才能拿到新餐巾,其费用为 $c_2$ 。例如,将一块第 $k$ 天使用过的餐巾送到清洗店A清洗,则可以在第 $k+m_1$ 天使用。 请为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

输入输出格式

输入格式


第一行,包含六个个正整数 $n, m_1, m_2, c_1, c_2, p$ 。 接下来输入 $n$ 行,每行包含一个正整数 $r_i$ 。

输出格式


输出一行,包含一个正整数,表示最小的总花费。

输入输出样例

输入样例 #1

4 1 2 2 1 3
8
2
1
6

输出样例 #1

35

说明

**【样例说明】** 第 1 天:买8块餐巾,花费24。送2块餐巾去清洗店A,6块餐巾去清洗店B。 第 2 天:取回2块清洗店A的餐巾,花费4。送1块餐巾去清洗店B。 第 3 天:取回6块清洗店B的餐巾,花费6。 第 4 天:取回1块清洗店B的餐巾,花费1。这样就用了最少的钱。 **【数据规模和约定】** 对于30%的数据,$1 \leq n \leq 5$ ,$1 \leq c_1, c_2, p \leq 5$ , $1 \leq r_i \leq 5$ 。 对于50%的数据,$1 \leq n \leq 100$ ,$1 \leq r_i \leq 50$ 。 对于70%的数据,$1 \leq n \leq 5000$ 。 对于100%的数据,$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$ 。