Tích ba số nguyên với ba số hạng của dãy

Cho dãy số $A$ gồm $N$ số nguyên $A_1, A_2, \dots, A_N$ $(N \ge 3)$ và 3 số nguyên $x, y, z$. Trong dãy số $A$, hãy chọn 3 số hạng $A_i, A_j, A_k$ $(1 \le i < j < k \le N)$ sao cho $S = x \times A_i + y \times A_j + z \times A_k$ đạt giá trị lớn nhất.

Ví dụ, với dãy $A$ gồm 4 số hạng: $[1, 3, 2, 4]$; $x = 1, y = 1, z = 2$, ta có 4 cách chọn 3 số hạng trong dãy $A$:

• Chọn 3 số hạng: $A_1, A_2, A_3 = [1, 3, 2]$ thì tích $S = 1 \times 1 + 1 \times 3 + 2 \times 2 = 8$;
• Chọn 3 số hạng: $A_1, A_2, A_4 = [1, 3, 4]$ thì tích $S = 1 \times 1 + 1 \times 3 + 2 \times 4 = 12$;
• Chọn 3 số hạng: $A_1, A_3, A_4 = [1, 2, 4]$ thì tích $S = 1 \times 1 + 1 \times 2 + 2 \times 4 = 11$;
• Chọn 3 số hạng: $A_2, A_3, A_4 = [3, 2, 4]$ thì tích $S = 1 \times 3 + 1 \times 2 + 2 \times 4 = 13$;

Như vậy giá trị lớn nhất của $S$ có thể đạt được là 13.

Dữ liệu cho trong tệp văn bản TichBaSo.Inp gồm:

• Dòng thứ nhất ghi số nguyên dương $N$ là số các số hạng của dãy $A$.
• Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ $(|A_i| \le 10^5$ với $i = 1, 2, 3, \dots, N)$.
• Dòng thứ ba ghi 3 số nguyên $x, y, z$, $(|x|, |y|, |z| \le 10^5)$.

Các số ghi trên một dòng được cách nhau bởi dấu cách.

Kết quả ghi ra file văn bản TichBaSo.Out gồm một số nguyên là giá trị lớn nhất của $S$ có thể đạt được.

• Có 50% số test ứng với 50% số điểm thỏa mãn $N \le 200$;
• Có 25% số test ứng với 25% số điểm thỏa mãn $200 < N \le 2 \times 10^5$ và $x = y = z$;
• Có 25% số test ứng với 25% số điểm thỏa mãn $200 < N \le 2 \times 10^5$ và $|x|, |y|, |z| \le 10^5$.