有

个元素

,可以将

个元素分成多组,每组的元素编号必须是连续的.

设每组的

为

,则每组的价值公式为

.

求最大价值和.

Input

输入由三行组成。

第一行包含一个整数,表示士兵的总数.

第二行包含三个整数

,价值公式中各项的系数.

第三行包含

个用空格分隔的整数

.

Output

输出一个整数，，表示最大价值和。

Sample Input

4

-1 10 -20

2 2 3 4

Sample Output

9

HINT

 

Solution

表示前

个的最大价值和,

.

这样是

的,显然过不了,所以考虑斜率优化.

当

且

时,

尽量将

分离:

设

,

则

,

.

的前提条件是

.

整理得,

.