题目描述

一个餐厅在相继的 $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$。