题目描述

幼儿园中的玩具，白天供小朋友们玩，晚上可以拿去消毒。

下来 $D \ (1 \le D \le 10^5)$ 天 ，幼儿园每天需要的玩具数量为 $T_i \ (1 \le T_i \le 50)$ 个玩具。

一开始幼儿园没有玩具，每个玩具售价为 $Tc \ (1 \le Tc \le 60)$ 。

消毒服务有两种：

• 第一个服务收费 $C1$ ，需要 $N1$ 个晚上完成；

• 第二个服务收费 $C2$ ，需要 $N2$ 个晚上完成。

$(1 \le N1,N2 \le D ; 1 \le C1 ， C2 \le 60)$

将玩具送去消毒，如果是一个晚上的服务，可以在第二天早上支付并取回玩具，或者如果需要更多晚上的消毒，则在之后的早晨取回。

求在下来 $D$ 天幼儿园总花费的最小值（含购买玩具和玩具消毒的费用）。

输入格式

第 1 行六个整数：$D, N1, N2, C1, C2, Tc$ 。

下来 $D$ 个整数 $T_i$ 。

• 70% 数据满足 $1 \le D \le 500$

输出格式

一行一个整数，表示总花费的最小值。

输入

4 1 2 2 1 3 
8 
2 
1 
6

输出

35

说明/提示

贝茜希望庆祝 4 天，第一天需要 8 个玩具，第二天需要 2 个玩具，第三天需要 1 个玩具，第四天需要 6 个玩具。第一个消毒服务需要 1 天，收费 2 美元，第二个需要 2 天，收费 1 美元。购买一个新玩具需要 3 美元。

第 1 天 早上购买 8 个玩具，花费 24 美元；下午开派对。将 2 个玩具送去快速清洗（过夜），其余 6 个玩具送去慢速清洗（两晚）。

第 2 天 从快速清洗处取回 2 个玩具；支付 4 美元。下午开派对。将 1 个玩具送去慢速清洗。

第 3 天 从慢速清洗处取回 6 个玩具并支付 6 美元。下午开派对。

第 4 天 从慢速清洗处取回最后一个玩具（将现场玩具数量恢复到 6 个）；支付 1 美元。开心地开派对，意识到花费了最少的钱。