题目背景

本题和网络流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$ 。

输出格式

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

4 1 2 2 1 3
8
2
1
6

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$ 。