Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và hai số nguyên \(w_1, w_2\). Một bộ năm chỉ số \(1 \le i_1 < i_2 < i_3 < i_4 < i_5 \le n\) có trọng số được tính bằng công thức:

Ví dụ: Với dãy gồm \(7\) số nguyên \(2, 8, 1, 9, 1, -1, 8\) và \(w_1 = 1, w_2 = -1\), bộ năm chỉ số \(2, 3, 4, 6, 7\) có trọng số bằng \((1 \cdot 8) + (-1 \cdot 1) + 9 + (-1 \cdot (-1)) + (1 \cdot 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 của dãy này.

Yêu cầu

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và hai số nguyên \(w_1, w_2\). Hãy tìm bộ năm có trọng số lớn nhất.

Input

• Dòng đầu chứa ba số nguyên \(n, w_1, w_2\) (\(n \ge 5; |w_1|, |w_2| \le 100\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\) với \(i = 1, 2, \dots, n\)).

Output

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

Example

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

25

7 0 0
2 8 1 9 1 -1 8

9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^5; w_1 = w_2 = 0\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 5000; w_1 = 0; w_2 < 0\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5; w_1 = 0; w_2 < 0\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^5\), không có ràng buộc gì thêm.

Nguồn: 3D'17