Problem Statement

You are given an array a of N non-zero integers and a sign bonus B . Your task is to select a subsequence of a such that the signs of the chosen elements strictly alternate . This means the subsequence can follow a pattern like (positive, negative, positive, ...) or (negative, positive, negative, ...). The score of a subsequence is calculated as the sum of its elements plus a bonus for each alternation . Specifically, if the subsequence has length L : If L < 2 , the bonus is 0 . If L ≥ 2 , the bonus is B × (L - 1) . Find the maximum possible score achievable . Note: You may choose an empty subsequence. The score of an empty subsequence is defined as 0. Input Format The first line contains a integer, N , denoting the number of elements in the array. The second line contains a integer, B , denoting the bonus value for each alternation. Each line i of the N subsequent lines (where 0 ≤ i < N ) contains a integer, a[i] . Constraints 1 ≤ N ≤ 10^5 0 ≤ B ≤ 10^9 -1