Trên dãy số nguyên a1, a2, … , an và với hai số nguyên w1 và w2, ta định nghĩa một bộ năm chỉ số 1 ≤ i1 < i2 < …< i5 ≤ n được gọi là một bộ năm và có trọng số được tính bằng: (w1 × a[i1] ) +(w2 × a[i2] ) + a[i3] + (w2 × a[i4] ) + (w1 × a[i5] ). Ví dụ, trên dãy gồm 7 số nguyên 2, 8, 1, 9, 1, −1, 8 và w1 = 1, w2 = −1 thì bộ năm chỉ số 2, 3, 4, 6, 7 là một bộ năm và có trọng số bằng (1 × 8) + (−1 × 1) + 9 + (−1 × (−1)) +(1 × 8) = 25, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số nguyên a1, a2, … , an và với hai số nguyên w1 và w2. Hãy tìm bộ năm có trọng số lớn nhất.

Dữ liệu:

• Dòng đầu chứa ba số nguyên 𝑛, 𝑤1, 𝑤2 (𝑛 ≥ 5; |𝑤1|, |𝑤2| ≤ 100);

• Dòng thứ hai chứa 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 (|𝑎𝑖| ≤ 10^9 với 𝑖 = 1, 2, … , 𝑛).

Kết quả:

• gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Sample Input

7 1 -1 
2 8 1 9 1 -1 8

Sample Output

25

Ràng buộc:

- Có 20% số lượng test thỏa mãn điều kiện: 𝑛 ≤ 100; 
- Có thêm 20% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 10^5; 𝑤1 = 𝑤2 = 0; 
- Có thêm 20% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 5000; 𝑤1 = 0; 𝑤2 < 0; 
- Có thêm 20% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 10^5; 𝑤1 = 0; 𝑤2 < 0; 
- Có 20% số lượng test còn lại thỏa mãn điều kiện: 𝑛 ≤ 10^5.