Marvolo Gaunt's Ring

 

Description

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·ai + q·aj + r·ak for given p, q, r and array a1, a2, ... an 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 ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105).

Next line of input contains n space separated integers a1, a2, ... an ( - 109 ≤ ai ≤ 109).

Output

Output a single integer the maximum value of p·ai + q·aj + r·ak that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.

Sample Input

Input

5 1 2 3
1 2 3 4 5

Output

30

Input

5 1 2 -3
-1 -2 -3 -4 -5

Output

12

Hint

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.

题意：

邓布利多教授正在帮助哈利摧毁魂器。当他怀疑一个魂器出现在那里时，他去了冈特沙克。他看到Marvolo Gaunt的戒指，并将其确定为魂器。虽然他摧毁了它，但仍然受到诅咒的影响。斯内普教授正在帮助邓布利多解除诅咒。为此，他想给Dumbledore提供他制作的药水x滴。

x的值被计算为给定p，q，r和阵列a1，a2，......的p·ai + q·aj + r·ak的最大值，使得1≤i≤j≤k≤n。帮助Snape找到x的值。请注意x的值可能是负数。

思路：

开两个数组，前缀数组表示到第i个数为止，p*a[i]的最大值。后缀数组表示到第i个数为止，r*a[i]的最大值。

如何再加上中间的q*a[i]计算最大值。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
const int maxn=1e5+10;
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;



int main()
{
    ll a[maxn];
    ll left[maxn],right[maxn];

    ll n,p,q,r;
    cin>>n>>p>>q>>r;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }

    left[1]=p*a[1];

    for(int i=2; i<=n; i++)
    {
        left[i]=max(left[i-1],p*a[i]);
    }
    right[n]=r*a[n];

    for(int i=n-1; i>=1; i--)
    {
        right[i]=max(right[i+1],r*a[i]);
    }

    ll ans=-INF;
    for(int i=1; i<=n; i++)
    {
        ans=max(ans,left[i]+right[i]+q*a[i]);
    }
    cout<<ans<<endl;
    return 0;
}