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 static java.lang.Math.*;
 
import java.io.DataInputStream; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.math.BigInteger; 
 
public class Main 
{ 
 
	static int mod = 1000000007;
	static int MOD = 1000000007;
	static int temp = 998244353;
	static final long M = (int)1e9+7;
 
	
	static class Pair implements Comparable<Pair>
	{
		int first, second;
		public Pair(int aa, int bb)
		{
			first = aa; second = bb;
		}
		public int compareTo(Pair p)
		{
//			if(a == p.a) return b - p.b;
//			return a - p.a;
			if(first == p.first) return second - p.second;
			return first - p.first;
		}
	}
	
	/*
	 * IO FOR 2D GRID IN JAVA
	 * char[][] arr = new char[n][m]; //grid in Q.
			
			for(int i = 0;i<n;i++)
			{
				char[] nowLine = sc.next().toCharArray();
				for(int j = 0;j<m;j++)
				{
					arr[i][j] = nowLine[i];
				}
			}
	 * */
	
	static class Reader 
	{ 
		final private int BUFFER_SIZE = 1 << 16; 
		private DataInputStream din; 
		private byte[] buffer; 
		private int bufferPointer, bytesRead; 
 
		public Reader() 
		{ 
			din = new DataInputStream(System.in); 
			buffer = new byte[BUFFER_SIZE]; 
			bufferPointer = bytesRead = 0; 
		} 
 
		public Reader(String file_name) throws IOException 
		{ 
			din = new DataInputStream(new FileInputStream(file_name)); 
			buffer = new byte[BUFFER_SIZE]; 
			bufferPointer = bytesRead = 0; 
		} 
 
		public String next() throws IOException 
		{ 
			byte[] buf = new byte[64]; // line length 
			int cnt = 0, c; 
			while ((c = read()) != -1) 
			{ 
				if (c == '\n') 
					break; 
				buf[cnt++] = (byte) c; 
			} 
			return new String(buf, 0, cnt); 
		} 
		
		public int nextInt() throws IOException 
		{ 
			int ret = 0; 
			byte c = read(); 
			while (c <= ' ') 
				c = read(); 
			boolean neg = (c == '-'); 
			if (neg) 
				c = read(); 
			do
			{ 
				ret = ret * 10 + c - '0'; 
			} while ((c = read()) >= '0' && c <= '9'); 
 
			if (neg) 
				return -ret; 
			return ret; 
		}
		
		int[] readArray(int n) throws IOException {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
 
		public long nextLong() throws IOException 
		{ 
			long ret = 0; 
			byte c = read(); 
			while (c <= ' ') 
				c = read(); 
			boolean neg = (c == '-'); 
			if (neg) 
				c = read(); 
			do { 
				ret = ret * 10 + c - '0'; 
			} 
			while ((c = read()) >= '0' && c <= '9'); 
			if (neg) 
				return -ret; 
			return ret; 
		} 
 
		public double nextDouble() throws IOException 
		{ 
			double ret = 0, div = 1; 
			byte c = read(); 
			while (c <= ' ') 
				c = read(); 
			boolean neg = (c == '-'); 
			if (neg) 
				c = read(); 
 
			do { 
				ret = ret * 10 + c - '0'; 
			} 
			while ((c = read()) >= '0' && c <= '9'); 
 
			if (c == '.') 
			{ 
				while ((c = read()) >= '0' && c <= '9') 
				{ 
					ret += (c - '0') / (div *= 10); 
				} 
			} 
 
			if (neg) 
				return -ret; 
			return ret; 
		} 
 
		private void fillBuffer() throws IOException 
		{ 
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
			if (bytesRead == -1) 
				buffer[0] = -1; 
		} 
 
		private byte read() throws IOException 
		{ 
			if (bufferPointer == bytesRead) 
				fillBuffer(); 
			return buffer[bufferPointer++]; 
		} 
 
		public void close() throws IOException 
		{ 
			if (din == null) 
				return; 
			din.close(); 
		}
 
		public BigInteger nextBigInteger() {
			// TODO Auto-generated method stub
			return null;
		}
 
	}
 
	
	public static boolean isPrime(long n) {
		if(n == 1)
		{
			return false;
		}
		for(long i = 2;i*i<=n;i++)
		{
			if(n%i == 0)
			{
				return false;
			}
		}
		return true;
	}
	
	public static List<Integer> Sieve(int n)
	{
		boolean prime[] = new boolean[n+1];
		Arrays.fill(prime, true);
		List<Integer> l = new ArrayList<>();
		
		
		for (int p=2; p*p<=n; p++) 
		{ 
			if (prime[p] == true) 
			{ 	
			    for(int i=p*p; i<=n; i += p) 
				{
				    prime[i] = false; 
				}	
			} 
		} 
 
		for (int p=2; p<=n; p++) 
		{
		    if (prime[p] == true)
		    {
		       l.add(p); 
		    }
		}
		
		return l;
	}
	
	
	public static int gcd(int a, int b)
	{
		if(b == 0)
		 return a;
		
		else
		return gcd(b,a%b);
	}
	
	public static long LongGCD(long a, long b)
	{
		if(b == 0)
			 return a;
			
			else
			return LongGCD(b,a%b);
	}
 
 
	public static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }
	
	public static int phi(int n)  //euler totient function
    { 
        int result = 1; 
        for (int i = 2; i < n; i++) 
            if (gcd(i, n) == 1) 
                result++; 
        return result; 
    }
	
	    
	public static int[] computePrefix(int arr[], int n)
	{
		int[] prefix = new int[n];
		prefix[0] = arr[0];
		for(int i = 1;i<n;i++)
		{
			prefix[i] = prefix[i-1]+arr[i];
		}
		
		return prefix;
	}
	
	
	public static int fastPow(int x, int n) //include mod at each step if asked and in args of fn too
	{
		if(n == 0)
			return 1;
		else if(n%2 == 0)
			return fastPow(x*x,n/2);
		else
			return x*fastPow(x*x,(n-1)/2);
	}
	
	
	   public static long power(long x, long y, long p)
	    {
	 
	        long res = 1;
	 
	        x = x % p;
	 
	        while (y > 0) {
	            if (y % 2 == 1)
	                res = (res * x) % p;
	 
	            y = y >> 1; 
	            x = (x * x) % p;
	        }
	 
	        return res;
	    }
	   
	   static long modInverse(int n, int p)
	    {
	        return power(n, p - 2, p);
	    }
	 
	    // Returns nCr % p using Fermat's little theorem.
	    
	    public static long nCr(int n, int r,
	                             int p)
	    {
	 
	          if (n<r) 
	              return 0;
	          
	        if (r == 0)
	            return 1;
	 
	        int[] fac = new int[n + 1];
	        fac[0] = 1;
	 
	        for (int i = 1; i <= n; i++)
	            fac[i] = fac[i - 1] * i % p;
	 
	        return (fac[n] * modInverse(fac[r], p)
	                % p * modInverse(fac[n - r], p)
	                % p)
	            % p;
	    }
	 
 
		public static int LowerBound(int a[], int x) {
			  int l=-1,r=a.length;
			  while(l+1<r) {
			    int m=(l+r)>>>1;
			    if(a[m]>=x) r=m;
			    else l=m;
			  }
			  return r;
			}
		
		
		public static int UpperBound(int a[], int x) {
		    int l=-1,r=a.length;
		    while(l+1<r) {
		       int m=(l+r)>>>1;
		       if(a[m]<=x) l=m;
		       else r=m;
		    }
		    return l+1;
		}
		
		public static void Sort(int[] a) {
			List<Integer> l=new ArrayList<>();
			for (int i:a) l.add(i);
			Collections.sort(l);
			//Collections.reverse(l);  //Use to Sort decreasingly 
			for (int i=0; i<a.length; i++) a[i]=l.get(i);
		}
		
		//MODULO OPS for addition and multiplication 
		
		   public static long perfomMod(long x){
		        return ((x%M + M)%M);
		    }
		   public static long addMod(long a, long  b){
		        return perfomMod(perfomMod(a)+perfomMod(b));
		    }
		   public static long mulMod(long  a, long b){
		        return perfomMod(perfomMod(a)*perfomMod(b));
		   }
		   public static int n,x;
		   
		   public static long solve(int[] arr, int n , long x)
		   {
			   long[][][] dp = new long[n+1][2][2];
			   for(int i = 0;i<=n;i++)
			   {
				   for(int j = 0;j<2;j++)
				   {
					  Arrays.fill(dp[i][j], 0);
				   }
			   }
			   
			   dp[0][1][0] = arr[0];
			   dp[0][1][1] = x * arr[0];
			   
			   long ans = max(0L,max(1L * arr[0],x * arr[0]));
			   for(int i = 1;i<n;i++)
			   {
				   dp[i][1][0] = max(1L * arr[i],arr[i] + dp[i-1][1][0]);
				   dp[i][1][1] = max(x * arr[i],x * arr[i] + max(dp[i-1][1][1],dp[i-1][1][0]));
				   dp[i][0][0] = max(1L * arr[i],arr[i] + max(dp[i-1][1][1],dp[i-1][0][0]));
				   ans = max(ans,max(dp[i][1][0],max(dp[i][1][1],dp[i][0][0])));
			   }
			   
			   return ans;
		   }
		   
		public static void main(String[] args) throws IOException 
		{ 
			Reader sc = new Reader();
			PrintWriter out = new PrintWriter(System.out);
			
			n = sc.nextInt();
			x = sc.nextInt();
			int[] arr = sc.readArray(n);
			
			System.out.println((solve(arr,n,x)));
			
			out.close();
		}
}
 
 
 