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.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }
}

class Task {

    static int MOD = 1000000007;
//    List<List<Integer>> g = new ArrayList<>();
//    int n;
    //    char[] s;
//    int a[];
//    boolean used[];


    public void solve(Scanner in, PrintWriter out) {
        int n = in.nextInt();
        long x = in.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
        }

        long s = 0;
        long sai = 0;
        long saif = 0;
        long f = 0;
        for (int i = 0; i < n; i++) {
            long oldS = s;
            long oldSai = sai;
            s = Math.max(a[i], s + a[i]);
            sai = Math.max(oldS + a[i] * x, Math.max(sai + a[i] * x, a[i] * x));
            saif = Math.max(saif + a[i], Math.max(oldSai + a[i], a[i]));
            f = Math.max(f, saif);
            f = Math.max(f, sai);
            f = Math.max(f, s);

//            System.out.println("s = " + s);
//            System.out.println("sai = " + sai);
//            System.out.println("saif = " + saif);
//            System.out.println("f = " + f);
        }

//        System.out.println("s = " + s);
//        System.out.println("f = " + f);
        System.out.println(f);
    }
}

class Utils {

    public static int binarySearch(int[] a, int key) {
        int s = 0;
        int f = a.length;
        while (f > s) {
            int mid = (s + f) / 2;
            if (a[mid] > key) {
                f = mid - 1;
            } else if (a[mid] <= key) {
                s = mid + 1;
            }
        }
        return -1;
    }

    public static long gcd(long a, long b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    static List<Integer> prime(int number) {
        List<Integer> a = new ArrayList<>();
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                a.add(i);
                number /= i;
                i = 1;
            }
        }
        a.add(number);
        return a;
    }
}

class Pair<T, U> {
    public T a;
    public U b;

    public Pair(T a, U b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Pair<?, ?> pair = (Pair<?, ?>) o;

        if (a != null ? !a.equals(pair.a) : pair.a != null) return false;
        return b != null ? b.equals(pair.b) : pair.b == null;
    }

    @Override
    public int hashCode() {
        int result = a != null ? a.hashCode() : 0;
        result = 31 * result + (b != null ? b.hashCode() : 0);
        return result;
    }
}


class Vect {
    public int a;
    public int b;

    public Vect(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Vect vect = (Vect) o;

        if (a != vect.a) return false;
        return b == vect.b;
    }

    @Override
    public int hashCode() {
        int result = a;
        result = 31 * result + b;
        return result;
    }
}

class Tri {
    public int a;
    public int b;
    public int c;

    public Tri(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

class Triple<T, U, P> {
    public T a;
    public U b;
    public P c;

    public Triple(T a, U b, P c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Triple<?, ?, ?> triple = (Triple<?, ?, ?>) o;

        if (a != null ? !a.equals(triple.a) : triple.a != null) return false;
        return b != null ? b.equals(triple.b) : triple.b == null;
    }

    @Override
    public int hashCode() {
        int result = a != null ? a.hashCode() : 0;
        result = 31 * result + (b != null ? b.hashCode() : 0);
        return result;
    }
}


class Scanner {
    BufferedReader in;
    StringTokenizer tok;

    public Scanner(InputStream in) {
        this.in = new BufferedReader(new InputStreamReader(in));
        tok = new StringTokenizer("");
    }

    private String tryReadNextLine() {
        try {
            return in.readLine();
        } catch (Exception e) {
            throw new InputMismatchException();
        }
    }

    public String nextToken() {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(next());
        }
        return tok.nextToken();
    }

    public String next() {
        String newLine = tryReadNextLine();
        if (newLine == null)
            throw new InputMismatchException();
        return newLine;
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() {
        return Long.parseLong(nextToken());
    }
}