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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sumit
 */
public class Main {
      public static void main(String[] args) {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            InputReader in = new InputReader(inputStream);
            OutputWriter out = new OutputWriter(outputStream);
            DBeautifulArray solver = new DBeautifulArray();
            solver.solve(1, in, out);
            out.close();
      }

      static class DBeautifulArray {
            public void solve(int testNumber, InputReader in, OutputWriter out) {
                  int n = in.nextInt();
                  long x = in.nextInt();
                  long arr[] = in.nextLongArray(n);
                  long left[] = new long[n];
                  long right[] = new long[n];
                  long sum[] = new long[n];
                  sum[0] = arr[0];
                  if (arr[0] > 0)
                        left[0] = arr[0];
                  for (int i = 1; i < n; i++) {
                        sum[i] = arr[i] + sum[i - 1];
                        left[i] = left[i - 1] + arr[i];
                        if (left[i] < 0)
                              left[i] = 0;
                  }
                  if (arr[n - 1] > 0)
                        right[n - 1] = arr[n - 1];
                  for (int i = n - 2; i >= 0; i--) {
                        right[i] = right[i + 1] + arr[i];
                        if (right[i] < 0)
                              right[i] = 0;
                  }


                  long max = Math.max(arr[0], x * arr[0]);
                  if (n > 1)
                        max += right[1];
                  long curr = 0;
                  for (int i = 1; i < n; i++) {
                        curr = Math.max(curr, left[i - 1] - (x * sum[i - 1]));
                        if (i < n - 1)
                              max = Math.max(curr + right[i + 1] + (x * sum[i]), max);
                        else
                              max = Math.max(curr + (x * sum[i]), max);
                  }
                  if (max < 0)
                        max = 0;
                  out.printLine(max);


            }

      }

      static class OutputWriter {
            private final PrintWriter writer;

            public OutputWriter(OutputStream outputStream) {
                  writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }

            public OutputWriter(Writer writer) {
                  this.writer = new PrintWriter(writer);
            }

            public void close() {
                  writer.close();
            }

            public void printLine(long i) {
                  writer.println(i);
            }

      }

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

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

            public int read() {
                  if (numChars == -1)
                        throw new InputMismatchException();

                  if (curChar >= numChars) {
                        curChar = 0;
                        try {
                              numChars = stream.read(buf);
                        } catch (IOException e) {
                              throw new InputMismatchException();
                        }
                        if (numChars <= 0)
                              return -1;
                  }

                  return buf[curChar++];
            }

            public int nextInt() {
                  int c = read();

                  while (isSpaceChar(c))
                        c = read();

                  int sgn = 1;

                  if (c == '-') {
                        sgn = -1;
                        c = read();
                  }

                  int res = 0;

                  do {
                        if (c < '0' || c > '9')
                              throw new InputMismatchException();

                        res *= 10;
                        res += c & 15;

                        c = read();
                  } while (!isSpaceChar(c));

                  return res * sgn;
            }

            public long nextLong() {
                  int c = read();

                  while (isSpaceChar(c))
                        c = read();

                  int sign = 1;

                  if (c == '-') {
                        sign = -1;

                        c = read();
                  }

                  long result = 0;

                  do {
                        if (c < '0' || c > '9')
                              throw new InputMismatchException();

                        result *= 10;
                        result += c & 15;

                        c = read();
                  } while (!isSpaceChar(c));

                  return result * sign;
            }

            public long[] nextLongArray(int arraySize) {
                  long array[] = new long[arraySize];

                  for (int i = 0; i < arraySize; i++)
                        array[i] = nextLong();

                  return array;
            }

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

      }
}

