(tich3so.*)

Cho dãy số \(A\) gồm \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}(n \geq 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 \leq i < j < k \leq 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 \(\lbrack 1,3,2,4\rbrack\); \(x = 1,y = 1,z = 2\), ta có 4 cách chọn 3 số hạng trong dãy \(A\):

• Chọn \(a_{1},a_{2},a_{3} = \lbrack 1,3,2\rbrack\) thì tích \(S = 1 \times 1 + 1 \times 3 + 2 \times 2 = 8\);

• Chọn \(a_{1},a_{2},a_{4} = \lbrack 1,3,4\rbrack\) thì tích \(S = 1 \times 1 + 1 \times 3 + 2 \times 4 = 12\);

• Chọn \(a_{1},a_{3},a_{4} = \lbrack 1,2,4\rbrack\) thì tích \(S = 1 \times 1 + 1 \times 2 + 2 \times 4 = 11\);

• Chọn \(a_{2},a_{3},a_{4} = \lbrack 3,2,4\rbrack\) 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ể là 13.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\) là số lượng các số hạng của dãy \(A\);

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (\left| a_{i} \right| \leq 10^{5})\);

+ Dòng thứ ba ghi các số nguyên \(x,\ y,\ z\).

Kết quả:

+ Ghi một số nguyên duy nhất cho biết giá trị lớn nhất của \(S\) có thể đạt được.

Ví dụ:

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(n \leq 200\);

+ Có 25% số test khác tương ứng 25% số điểm có \(200 < n \leq 2 \times 10^{5}\) và \(x = y = z\).

+ Có 25% số test còn lại tương ứng 25% số điểm có \(200 < n \leq 2 \times 10^{5}\) và \(|x|,\ |y|,|z| \leq 10^{5}\).