[HNOI2001] 软件开发

题目描述

某软件公司正在规划一项 $n$ 天的软件开发计划，根据开发计划第 $i$ 天需要 $n_i$ 个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。

消毒方式有两种，$A$ 种方式的消毒需要 $a$ 天时间，$B$ 种方式的消毒需要 $b$ 天，$A$ 种消毒方式的费用为每块毛巾 $f_A$, $B$ 种消毒方式的费用为每块毛巾 $f_B$，而买一块新毛巾的费用为 $f$（新毛巾是已消毒的，当天可以使用）。公司经理正在规划在这 $n$ 天中，每天买多少块新毛巾、每天送多少块毛巾进行 $A$ 种消毒和每天送多少块毛巾进行 $B$ 种消毒。当然，公司经理希望费用最低。

你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行 $A$ 种消毒和多少毛巾进行 $B$ 种消毒，使公司在这项 $n$ 天的软件开发中，提供毛巾服务的总费用最低。

输入格式

第一行为六个整数 $n,a,b,f,f_A,f_B$。

第二行为 $n$ 个整数 $n_1,n_2,\ldots,n_n$。

输出格式

仅一个整数，为最少的费用。

样例 #1

样例输入 #1

4  1  2  3  2  1                         
8  2  1  6

样例输出 #1

38

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $b>a$，$f>f_A>f_B$，$1\le f,f_A,f_B\le 60$，$1\le n\le 10^3$。