Cho dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ và 3 số nguyên ~x~, ~y~, ~z~. Tìm giá trị lớn nhất của biểu thức ~x \times a_i + y \times a_j + z \times a_k~ (~1 \le i < j < k \le n~).

Dữ liệu

• Dòng đầu chứa 4 số nguyên ~n, x, y, z~. (~3 \le n \le 10^6; |x|, |y|, |z| \le 10^9~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~).

Kết quả

Dòng duy nhất là giá trị lớn nhất tìm được.

Ràng buộc

• 40%: ~n \le 10^2~.
• 30%: ~10^2 \le n \le 10^6, x = y = z~
• 30%: Không có ràng buộc gì thêm.

Ví dụ

Giải thích

Chọn 3 vị trí 2, 4, 5.