Description

 

Ada’s Demo Album

Problem Description

Ada, a CSIE student, is also an amateur songwriter. She recently writes a wonderful song consisting of N bars. To make this song more popular, she decides to cooperate with a record label.

In order to obtain a recording contract, she has to prepare a demo and submit it to a record label in hopes of being invited to record a full-length album in a professional recording studio. However, as a CSIE sophomore tortured by exploding assignments, she has no time to record an additional demo. Instead, she would like to simply submit a snatch of her N-barred song as a demo. A snatch of a song is valid if both the two following conditions hold:

• It can be obtained by removing several (possibly zero) bars from the beginning and several (possibly zero) bars from the end.
• It consists of at least 2 bars.

Before making an official submission, she has done some surveys in order to pick and present the best snatch to the record label. With valuable feedbacks and a statistical transformation, for the i-th bar (1 ≤ i ≤ N), its greatness can be specified with a value a_i. Note that though Ada’s song is wonderful, a_i may be non-positive since a statistical transformation has been applied.

Fortunately, Ada also knows how a demo is rated in a record label. As humans are biased, the first impression and the ending of a demo may weigh differently in one’s mind. More specifically, given x,y,z from the record label, if the `-th bar, (` + 1)-th bar, …, and the r-th bar of the song are submitted as the demo, its rating will be

Please help Ada determine which snatch should be picked to achieve the maximal rating.

Input

The first line of the input contains 4 integers N, x, y, z, denoting the number of bars in the original song and the coefficients used in rating evaluation.

The second line of the input contains N space-separated integers a₁,a₂,…,a_N, where the i-th integer denotes that greatness of the i-th bar.

• 2 ≤ N ≤ 2 × 10⁵
• 1 ≤ x,y,z ≤ 10⁴
• −10⁹ ≤ a_i ≤ 10⁹,∀i = 1,2,…,N

Test Group 0 (0 %) •   Sample Input Test Group 2 (40 %) •   x = y = z

Test Group 1 (10 %) •   N ≤ 2000 Test Group 3 (50 %) •   No Additional Constraint

Output

Please output an integer S indicating the maximal achievable rating.

Sample Input 1                            Sample Input 2                           Sample Input 3

6 1 1 1                                              8 59 4 87                                         3 5358 5926 3141

-12 7 -127 -1 -2 -7                                 0 8 -7 0 5 0 -2 9                            1 10000 100000000

Sample Output 1                          Sample Output 2                        Sample Output 3

-3                                                    1239                                               314159265358

Explanation

• In the first testcase, S achieves its maximum by taking (`,r) = (4,5), S = 1 · (−1) + 1 · (−2) = −3.
• In the second testcase, S achieves its maximum by taking (`,r) = (2,8), S = 59 · 8 + 4 · ((−7) + 0 + 5 + (−2)) + 87 · 9 = 1239.
• In the third testcase, S achieves its maximum by taking (`,r) = (1,3), S = 5358 · 1 + 5926 · 10⁴ + 3141 · 10⁸ = 314159265358.

Hint

Roses are red,

Violets are blue,

See the Test Group 2?

It’s a d´ej`a vu.