Bộ năm

Cho dãy số nguyên $a_1, a_2,..., a_n$ và hai số nguyên $w_1, w_2$. Một bộ năm chỉ số $i_1, i_2, i_3, i_4, i_5$ thỏa mãn điều kiện $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 công thức: $(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ụ, 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$ 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 chính 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.

Đầu vào:

• Dòng đầu chứa ba số nguyên $n, w_1, w_2$ ($5 \leq n \leq 10^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$).

Đầu ra:

• In 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.

Subtask (tham khảo)

• 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$.

Ví dụ 1:

Đầu vào:

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

Đầu ra:

25

Ví dụ 2:

Đầu vào:

7 0 0
2 8 1 9 1 -1 8

Đầu ra:

9