Cho dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, ..., 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\)).

Dữ liệu vào

• 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, ..., a_n\) (\(\vert{}a_i\vert{} \le 10^5\); \(1 \le i \le n\)).
• Dòng thứ ba chứa ba số nguyên \(x, y, z\) (\(\vert{}x\vert{}, \vert{}y\vert{}, \vert{}z\vert{} \le 10^5\)).

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là giá trị lớn nhất tìm được.

Ràng buộc

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

Ví dụ

Input

5
1 3 2 4 5
3 8 2

Output

51

Giải thích
Chọn ba số hạng \(a_2, a_4, a_5\).
Giá trị của biểu thức là: \(x \cdot a_2 + y \cdot a_4 + z \cdot a_5 = 3 \cdot 3 + 8 \cdot 4 + 2 \cdot 5 = 51\) (lớn nhất).