You are given an array a consisting of n integers. Beauty of array is the maximum sum of some consecutive subarray of this array (this subarray may be empty). For example, the beauty of the array [10, -5, 10, -4, 1] is 15, and the beauty of the array [-3, -5, -1] is 0.

You may choose at most one consecutive subarray of a and multiply all values contained in this subarray by x. You want to maximize the beauty of array after applying at most one such operation.

Input

The first line contains two integers n and x (1 ≤ n ≤ 3 ⋅ 10^5, -100 ≤ x ≤ 100) — the length of array a and the integer x respectively.

The second line contains n integers a_1, a_2, ..., a_n (-10^9 ≤ a_i ≤ 10^9) — the array a.

Output

Print one integer — the maximum possible beauty of array a after multiplying all values belonging to some consecutive subarray x.

Examples

Input


5 -2
-3 8 -2 1 -6


Output


22


Input


12 -3
1 3 3 7 1 3 3 7 1 3 3 7


Output


42


Input


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


Output


0

Note

In the first test case we need to multiply the subarray [-2, 1, -6], and the array becomes [-3, 8, 4, -2, 12] with beauty 22 ([-3, 8, 4, -2, 12]).

In the second test case we don't need to multiply any subarray at all.

In the third test case no matter which subarray we multiply, the beauty of array will be equal to 0.
import java.util.*;

import java.io.*;

public class B {
	static BufferedReader br;
	static PrintWriter pw;
	static int inf = (int) 1e9;
	static long mod = (long) 1e9 + 7;
	static int[] coin, k;
	static long[] cum;
	static int n, x;
	static long[] a;

	static long dp(int idx, int s, int sta) {
		if (idx == n || sta == 2)
			return 0;
		if (memo[sta][s][idx] != -1)
			return memo[sta][s][idx];
		long ans = 0;
		if (s == 0) {
			if (sta == 0) {
				ans = Math.max(dp(idx + 1, 0, 0), dp(idx + 1, 1, 1) + a[idx] * x);
				ans = Math.max(ans, dp(idx + 1, 0, 1) + a[idx]);
			} else if (sta == 1) {
				ans = Math.max(dp(idx + 1, 0, 2), dp(idx + 1, 0, 1) + a[idx]);
				ans = Math.max(ans, dp(idx + 1, 1, 1) + a[idx] * x);
			}
		} else if (s == 1) {
				ans = Math.max(dp(idx + 1, 0, 2), dp(idx + 1, 2, 1) + a[idx]);
				ans = Math.max(ans, dp(idx + 1, 1, 1) + a[idx] * x);
		} else {
			ans = Math.max(dp(idx + 1, 2, 2), dp(idx + 1, 2, 1) + a[idx]);
		}

		return memo[sta][s][idx] = ans;
	}

	public static void main(String[] args) throws NumberFormatException, IOException, InterruptedException {
		br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		pw = new PrintWriter(System.out);
		n = sc.nextInt();
		x = sc.nextInt();
		a = new long[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextLong();
		}
		memo = new long[3][3][n];
		Arrays.fill(memo[0][0], -1);
		Arrays.fill(memo[1][0], -1);
		Arrays.fill(memo[2][0], -1);
		Arrays.fill(memo[0][1], -1);
		Arrays.fill(memo[1][1], -1);
		Arrays.fill(memo[2][1], -1);
		Arrays.fill(memo[0][2], -1);
		Arrays.fill(memo[1][2], -1);
		Arrays.fill(memo[2][2], -1);

		pw.println(dp(0, 0, 0));
		pw.flush();
		pw.close();
	}

	static long[][][] memo;

	static int findmax(int[] a) {
		int max = -1;
		int c = 0;
		for (int i = 0; i < n; i++) {
			c += a[i];
		}
		max = c;
		for (int i = 0; i < a.length; i++) {
			c -= a[i];
			c += a[(n + i) % (2 * n)];
			max = Math.max(max, c);
		}
		return max;
	}

	static double pow(double a, int e) // O(log e)
	{
		double res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res *= a;
			a *= a;
			e >>= 1;
		}
		return res;
	}

	static boolean check(int x) {
		int c = 0;
		while (x > 0) {
			c += x % 10;
			x /= 10;
		}
		return c % 3 == 0;
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;

		SegmentTree(int[] in) {
			array = in;
			N = in.length - 1;
			sTree = new int[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				int ql = sTree[node << 1];
				int qr = sTree[node << 1 | 1];
				sTree[node] = ql + qr;
			}
		}

		void update_point(int index, int val) // O(log n)
		{
			index += N - 1;
			sTree[index] += val;
			while (index > 1) {
				index >>= 1;
				sTree[index] = sTree[index << 1] + sTree[index << 1 | 1];
			}
		}

		void update_range(int i, int j, int val) // O(log n)
		{
			update_range(1, 1, N, i, j, val);
		}

		void update_range(int node, int b, int e, int i, int j, int val) {
			if (i > e || j < b)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;
			} else {
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				int ql = sTree[node << 1];
				int qr = sTree[node << 1 | 1];
				sTree[node] = ql + qr;
			}

		}

		void propagate(int node, int b, int mid, int e) {
			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			lazy[node] = 0;
		}

		int query(int i, int j) {
			return query(1, 1, N, i, j);
		}

		int query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return 0;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			int q1 = query(node << 1, b, mid, i, j);
			int q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return q1 + q2;

		}

	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	// method to return LCM of two numbers
	static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	static double dis(int x, int y, int z, int w) {
		return Math.sqrt((x - z) * (x - z) + (y - w) * (y - w));
	}

	static int[] nxtarr() throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] a = new int[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		return a;
	}

	static long[] nxtarrLong() throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		long[] a = new long[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Long.parseLong(st.nextToken());
		}
		return a;
	}

	static class pair implements Comparable<pair> {
		long x;
		long y;

		public pair(long d, long u) {
			x = d;
			y = u;
		}

		@Override
		public int compareTo(pair o) {
//			// TODO Auto-generated method stub
//			if (y == o.y)
//				return x - o.x;
			return 0;
		}

	}

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

		public triple(int a, int b, int c) {
			x = a;
			y = b;
			z = c;
		}

		@Override
		public int compareTo(triple o) {
			// TODO Auto-generated method stub
			return x - o.x;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}
