Problem 2100. -- 还是采蘑菇

2100: 还是采蘑菇

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 207  Accepted: 27
[Submit][Status][Web Board]

Description

这天,BobAlice家做客,为了好好招待BobAlice决定带Bob去采蘑菇,然后晚上做蘑菇全席。路边1~n的位置长满了蘑菇,蘑菇有不同的品种,用ai表示。AliceBob先采一个,Bob采到之后他们就往回走,Alice可以和Bob在同一个位置采蘑菇或者在回去的路上采一个。(家在位置0处,Alice和Bob都能且只能采一个蘑菇)

AliceBob有不同的口味用pq表示,他们各自吃蘑菇的开心程度=自己的口味*自己采的蘑菇的品种。

那么问题来了,Alice与Bob两者的开心程度和最大为多少。

Input

多组样例测试。每组样例包含两行。

第一行输入n p q;

第二行输入n个数,表示位置i的蘑菇的品种为a[i]。

数据范围:1<=n<=100000;-1000000000<=ai,p,q<=1000000000;

Output

每组输出一行,一个整数,AliceBob的吃蘑菇开心程度和的最大值。

Sample Input

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

Sample Output

10
4

HINT

 样例解释:


样例1:Bob选5,Alice选5


样例2:Bob选2,Alice选-2

[Submit][Status][Web Board]