Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made. 

Value of x is calculated as maximum of p·ai + q·aj + r·ak for given p, q, r and array a1, a2, ... an such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.

Input

First line of input contains 4 integers n, p, q, r ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105).

Next line of input contains n space separated integers a1, a2, ... an ( - 109 ≤ ai ≤ 109).

Output

Output a single integer the maximum value of p·ai + q·aj + r·ak that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.

Examples

Input

5 1 2 3
1 2 3 4 5


Output

30


Input

5 1 2 -3
-1 -2 -3 -4 -5


Output

12

Note

In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	InputReader in;
	PrintWriter out;

	Main() throws IOException {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		// in = new InputReader(new FileInputStream("input_.txt"));
		// out = new PrintWriter(new File("output_.txt"));
		solve();
		out.close();
	}

	public static void main(String args[]) {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new Main();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	// --------------------My Code Starts Here----------------------
	long mod = (long) 1e9 + 7;
	double eps = 1e-5;

	public void solve() throws IOException {
		int n = in.nextInt();
		long p = in.nextInt();
		long q = in.nextInt();
		long r = in.nextInt();
		long seg1[] = new long[n + n];
		long seg2[] = new long[n + n];
		long a[] = new long[n];
		for (int i = 0; i < n; i++) {
			long val = in.nextLong();
			a[i] = val;
			add_max(seg1, i, val);
			add_min(seg2, i, val);
		}
		long ans = Long.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			long mid = q * a[i];
			long left = p;
			if (p > 0) {
				left *= max(seg1, 0, i);
			} else {
				left *= min(seg2, 0, i);
			}
			long right = r;
			if (r > 0) {
				right *= max(seg1, i, n - 1);
			} else {
				right *= min(seg2, i, n - 1);
			}
			ans = Math.max(ans, left + mid + right);
		}
		out.println(ans);
	}

	// ---------------------My Code Ends Here----------------------
	public static void add_max(long[] t, int i, long value) {
		i += t.length / 2;
		t[i] += value;
		for (; i > 1; i >>= 1)
			t[i >> 1] = Math.max(t[i], t[i ^ 1]);
	}

	// max[a, b]
	public static long max(long[] t, int a, int b) {
		long res = Long.MIN_VALUE;
		for (a += t.length / 2, b += t.length / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
			if ((a & 1) != 0)
				res = Math.max(res, t[a]);
			if ((b & 1) == 0)
				res = Math.max(res, t[b]);
		}
		return res;
	}

	public static void add_min(long[] t, int i, long value) {
		i += t.length / 2;
		t[i] += value;
		for (; i > 1; i >>= 1)
			t[i >> 1] = Math.min(t[i], t[i ^ 1]);
	}

	// max[a, b]
	public static long min(long[] t, int a, int b) {
		long res = Long.MAX_VALUE;
		for (a += t.length / 2, b += t.length / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
			if ((a & 1) != 0)
				res = Math.min(res, t[a]);
			if ((b & 1) == 0)
				res = Math.min(res, t[b]);
		}
		return res;
	}

	static long modulo(long a, long b, long c) {
		long x = 1;
		long y = a;
		while (b > 0) {
			if (b % 2 == 1) {
				x = (x * y) % c;
			}
			y = (y * y) % c; // squaring the base
			b /= 2;
		}
		return x % c;
	}

	static class Pair implements Comparable<Pair> {
		int x;
		int y;
		int z;

		Pair(int xx, int yy, int zz) {
			x = xx;
			y = yy;
			z = zz;
		}

		@Override
		public int compareTo(Pair o) {
			return Long.compare(this.y, o.y);
		}
	}

	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public final int nextInt() throws IOException {
			return (int) nextLong();
		}

		public final long nextLong() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
				if (c == -1)
					throw new IOException();
			}
			boolean negative = false;
			if (c == '-') {
				negative = true;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return negative ? (-res) : (res);
		}

		public final int[] readIntBrray(int size) throws IOException {
			int[] arr = new int[size];
			for (int i = 0; i < size; i++)
				arr[i] = nextInt();
			return arr;
		}

		public final String next() throws IOException {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final String nextLine() throws IOException {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (c != '\n' && c != -1);
			return res.toString();
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}
}