题目描述

有一家饭店，需要连续营业 $d$ 天。在第 $i$ 天，需要服务 $t_i$ 名顾客。每一名顾客需要使用一条干净的餐巾。

餐巾可以从商店购买，每件 $p$ 元。也可以将老的餐巾清洗循环使用。每天营业结束的傍晚将餐巾送去清洗，有两种方法

• 一种每件收费$a$元，要过 $s$ 个夜晚才能拿到；

• 另一种每件收费 $b$ 元，要过 $t$个夜晚。

每件餐巾可以任意选择一种清洗方法。清洗后可以保存起来，不必立即使用。

请问应该采购多少餐巾，怎样清洗，才能花最少的钱让所有顾客获得干净的餐巾？

输入格式

• 第一行：六个整数：$d$，$s$，$t$，$a$，$b$ 与 $p$，
• 第二行：$d$ 个整数：$t_1,t_2,\dots,t_d$

输出格式

• 单个整数表示答案

4 1 2 2 1 3
8
2
1
6

35

样例解释 1

第一天买8份，晚上送2件去快洗，6件去慢洗，第二天送1件去慢洗，最后两天不花钱

数据范围

• $50\%$ 的数据，$1\leq d\leq 100$
• $100\%$ 的数据，$1\leq d\leq 200,000$
• $1\leq p,a,b,\leq 10000$
• $1\leq t_i\leq 10000$