#203. 1221. [HNOI2001] 软件开发

1221. [HNOI2001] 软件开发

[HNOI2001] 软件开发

题目描述

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

消毒方式有两种,AA 种方式的消毒需要 aa 天时间,BB 种方式的消毒需要 bb 天,AA 种消毒方式的费用为每块毛巾 fAf_A, BB 种消毒方式的费用为每块毛巾 fBf_B,而买一块新毛巾的费用为 ff(新毛巾是已消毒的,当天可以使用)。公司经理正在规划在这 nn 天中,每天买多少块新毛巾、每天送多少块毛巾进行 AA 种消毒和每天送多少块毛巾进行 BB 种消毒。当然,公司经理希望费用最低。

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

输入格式

第一行为六个整数 n,a,b,f,fA,fBn,a,b,f,f_A,f_B

第二行为 nn 个整数 n1,n2,,nnn_1,n_2,\ldots,n_n

输出格式

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

样例 #1

样例输入 #1

4  1  2  3  2  1                         
8  2  1  6

样例输出 #1

38

提示

数据规模与约定

对于 100%100\% 的数据,保证 b>ab>af>fA>fBf>f_A>f_B1f,fA,fB601\le f,f_A,f_B\le 601n1031\le n\le 10^3