Bài 3 : Giá trị lớn nhất (6.0 điểm)

Cho dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) và ba số nguyên \(x,y,z\).

Yêu cầu: Tìm giá trị lớn nhất của biểu thức \(x \cdot a_i + y \cdot a_j + z \cdot a_k\) \((1 \le i < j < k \le n)\).

Input

Vào từ tệp văn bản BAI3.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương \(n\) \((3 \le n \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((|a_i| \le 10^5; 1 \le i \le n)\).
• Dòng thứ ba chứa ba số nguyên \(x,y,z\) \((|x|,|y|,|z| \le 10^5)\).

Output

Ghi ra tệp văn bản BAI3.OUT một số nguyên duy nhất là giá trị lớn nhất tìm được.

Example

5
1 3 2 4 5
3 8 2

51

Scoring

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thỏa mãn: \(n \le 10^2\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(10^2 < n \le 10^6\); \(x = y = z\).
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.