Description

一个餐厅在相继的\(N\)天里，第\(i\)天需要\(R_i\)块餐巾(\(i=(1,2,...,N)\))。餐厅可以从三种途径获得餐巾：

1. 购买新的餐巾，每块需\(p\)分；
2. 把用过的餐巾送到快洗部，洗一块需\(m\)天，费用需\(f\)分(\(f<p\))。如\(m=1\)时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
3. 把餐巾送到慢洗部，洗一块需\(n\)天(\(n>m\))，费用需s分(\(s<f\))。

在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量\(R_i\)，并使\(N\)天总的费用最小。

Input

输入文件共3行：
1. 第1行为总天数;
2. 第2行为每天所需的餐巾块数；
3. 第3行为每块餐巾的新购费用p，快洗所需天数m，快洗所需费用f，慢洗所需天数n，慢洗所需费用s。

Output

输出文件共1行为最小的费用。

Sample

Input

3
3 2 4
10 1 6 2 3

Output

64

Hint

• \(N\le 2000\)
• \(R_i\le 10000000\)
• \(p,f,s\le 10000\)
• 时限4s