Cho dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, \ldots, 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\) với \((1 \le i < j < k \le n)\).

Input

• 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, \ldots, 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

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