Cho dãy a gồm n số nguyên a₁, a₂, ..., 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 · a_i + y · a_j + z · a_k với điều kiện (1 ≤ i < j < k ≤ 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 ≤ n ≤ 10⁶).
- Dòng thứ hai chứa n số nguyên a₁, a₂, ..., a_n (|a_i| ≤ 10⁵; 1 ≤ i ≤ n).
- Dòng thứ ba chứa ba số nguyên x, y, z (|x|, |y|, |z| ≤ 10⁵).

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.

Scoring

- Có 40% số test ứng với 40% số điểm của bài thỏa mãn: n ≤ 10².
- Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: 10² < n ≤ 10⁶; 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.

Example

input

5
1 3 2 4 5
3 8 2

output

51

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