Mô tả đề bài

Trên dãy số nguyên ~a_1, a_2,..., a_n~ và với hai số nguyên, ~w_1, w_2~ ta định nghĩa một bộ năm chỉ số ~i_1, i_2, i_3, i_4, i_5~ sao cho: ~1 \leq i_1 < i_2 < i_3 < i_4 < i_5 \leq n~ được gọi là một bộ năm và có trọng số được tính bằng: $$ (w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_{i_3} + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5}) $$ Ví dụ, trên dãy gồm ~7~ số nguyên ~2, 8, 1, 9, 1, -1, 8~ và ~w_1 = 1, w_2 = -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 \times 8) + (-1 \times 1) + 9 + (-1 \times -1) + (1 \times 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 ~a_1, a_2,..., 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 format

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

Output format

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

Sample Input 1

7 0 0
2 8 1 9 1 -1 8

Sample Output 1

9

Sample Input 2

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

Sample Output 2

25

Subtasks

• Có ~20\%~ số lượng test thỏa mãn điều kiện: ~n \leq 100~;
• Có thêm ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 10^5, w_1 = w_2 = 0~;
• Có thêm ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 5000, w_1 = 0, w_2 < 0~;
• Có thêm ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 10^5, w_1 = 0, w_2 < 0~;
• Có ~20\%~ số lượng test còn lại thỏa mãn điều kiện: ~n \leq 10^5~.