Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly $*x*$ drops of the potion he made.

Value of $*x*$ is calculated as maximum of $*p*·*a*_{*i*} + *q*·*a*_{*j*} + *r*·*a*_{*k*}$ for given $*p*, *q*, *r*$ and array $*a*_{1}, *a*_{2}, ... *a*_{*n*}$ such that $1 ≤ *i* ≤ *j* ≤ *k* ≤ *n*$. Help Snape find the value of $*x*$. Do note that the value of $*x*$ may be negative.

Input

First line of input contains $4$ integers $*n*, *p*, *q*, *r*$ ($- 10^{9} ≤ *p*, *q*, *r* ≤ 10^{9}, 1 ≤ *n* ≤ 10^{5}$).

Next line of input contains $*n*$ space separated integers $*a*_{1}, *a*_{2}, ... *a*_{*n*}$ ($- 10^{9} ≤ *a*_{*i*} ≤ 10^{9}$).

Output

Output a single integer the maximum value of $*p*·*a*_{*i*} + *q*·*a*_{*j*} + *r*·*a*_{*k*}$ that can be obtained provided $1 ≤ *i* ≤ *j* ≤ *k* ≤ *n*$.

Note

In the first sample case, we can take $*i* = *j* = *k* = 5$, thus making the answer as $1·5 + 2·5 + 3·5 = 30$.

In second sample case, selecting $*i* = *j* = 1$ and $*k* = 5$ gives the answer $12$.