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 \le n \le 3 \cdot 10^5, -100 \le x \le 100$) — the length of array $a$ and the integer $x$ respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 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.

Difficulty: interview

Starter code:

Solutions:
N, X = list(map(int, input().split()))
A = [int(a) for a in input().split()]

dp = [[0]*4 for _ in range(N+1)]

for i in range(1, N+1):
    dp[i][0] = max(dp[i-1][0] + A[i-1], 0)
    dp[i][1] = max(dp[i-1][1] + A[i-1] * X, dp[i][0])
    dp[i][2] = max(dp[i-1][2] + A[i-1], dp[i][1])
    dp[i][3] = max(dp[i-1][3], dp[i][2])

print(dp[N][3])


n, x = list(map(int, input().split()))
cur1 = cur2 = cur = res = 0
for a in map(int, input().split()):
    cur1 = max(cur1 + a, 0)
    cur2 = max(cur2 + a * x, cur1)
    cur = max(cur + a, cur2)
    res = max(res, cur)
print(res)


n,x = map(int,input().split())
l = list(map(int,input().split()))
not_used = [0 for k in range(n+1)]
current = [0 for k in range(n+1)]
used =[0 for k in range(n+1)]
globalMax = 0
for k in range(n):
	not_used[k+1]= max(not_used[k],0)+l[k]
	current[k+1] = max(max(not_used[k],current[k]),0)+l[k]*x
	used[k+1] = max(max(current[k],used[k]),0)+l[k]
	globalMax = max(max(globalMax,used[k+1]),max(current[k+1],not_used[k+1]))
print(globalMax)

n, x = map(int, input().split())
dp1 = [0]*n
dp2 = [0]*n
dp0 = [0]*n
ans = 0
v = [int(i) for i in input().split()]
dp0[0] = max(0, v[0])
dp1[0] = v[0] * x
i = 0
ans = max(ans, dp1[i], dp2[i], dp0[i])
for i in range(1, n):
    dp0[i] = max(0, dp0[i - 1] + v[i])
    dp1[i] = max(dp1[i - 1] + v[i] * x, dp0[i-1] + v[i] * x)
    dp2[i] = max(dp1[i-1] + v[i], dp2[i - 1] + v[i])
    ans = max(ans, dp1[i], dp2[i], dp0[i])
print(ans)

n, x = map(int, input().split())
cur1=cur2=cur=res=0
for a in map(int, input().split()):
    cur1 = max(cur1 + a, 0)
    cur2 = max(cur2 + a * x, cur1)
    cur = max(cur + a, cur2)
    res = max(res, cur)
print(res)

N, X = list(map(int, input().split()))
a_list = list(map(int, input().split()))

dp = [[0] * 5 for _ in range(303030)]

for i in range(N):
    a = a_list[i]
    dp[i + 1][0] = 0
    dp[i + 1][1] = max(dp[i][1] + a, dp[i + 1][0])
    dp[i + 1][2] = max(dp[i][2] + a * X, dp[i + 1][1])
    dp[i + 1][3] = max(dp[i][3] + a, dp[i + 1][2])
    dp[i + 1][4] = max(dp[i][4], dp[i + 1][3])
print(dp[N][4])


def main():
    n, x = map(int, input().split())
    arr = list(map(int, input().split()))
    dp = [[0] * 5 for _ in range(n)]
    dp[0] = [arr[0], arr[0] * x, 0]
    ans = max(dp[0])
    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i])
        dp[i][1] = max(dp[i - 1][0] + arr[i] * x, arr[i] * x, dp[i - 1][1] + arr[i] * x)
        dp[i][2] = max(dp[i - 1][2] + arr[i], dp[i - 1][1] + arr[i])
        ans = max(ans, max(dp[i]))
    print(ans)
    return 0

main()

n, x = list(map(int, input().split()))
arr = [int(x) for x in input().split()]
dp = [[0 for _ in range(n)] for _ in range(3)]
dp[0][0] = max(arr[0], 0)
dp[1][0] = max(arr[0] * x, 0)
dp[2][0] = max(arr[0], 0)
answer = max(dp[0][0], dp[1][0], dp[2][0])
for i in range(1, n):
    dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i], 0)
    dp[1][i] = max(dp[0][i - 1] + arr[i] * x, dp[1][i - 1] + arr[i] * x, arr[i] * x, 0)
    dp[2][i] = max(dp[1][i - 1] + arr[i], dp[2][i - 1] + arr[i], arr[i], 0)
    answer = max(answer, dp[0][i], dp[1][i], dp[2][i])
print(answer)


#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code
from collections import Counter
from math import gcd

def __starting_point():
    n,x = map(int,input().split())
    a = list(map(int,input().split()))
    
    dp = [ [-1,-1,-1] for i in range(n)]

    dp[0][0] = a[0]
    dp[0][1] = x*a[0]
    dp[0][2] = a[0]
    m = max(dp[0][0],dp[0][1],dp[0][2],0)
    for i in range(1,n):
        dp[i][0] = max(dp[i-1][0]+a[i],a[i])
        dp[i][1] = max(dp[i-1][1] + x*a[i],x*a[i],dp[i-1][0]+x*a[i])
        dp[i][2] = max(dp[i-1][1] + a[i],a[i],dp[i-1][2]+a[i])
        m = max(max(dp[i]),m)
    print(m)
__starting_point()

n, x = list(map(int,input().split()))
l = list(map(int,input().split()))
b = [0] * n
f = [0] * n
pref = [0] * n
pref[0] = l[0]
for i in range(1, n):
	pref[i] = pref[i - 1] + l[i]
b[0] = x * l[0]
mini = 0
for i in range(1, n):
	mini = min(mini, pref[i - 1])
	b[i] = x * l[i] + max(b[i - 1], pref[i - 1] - mini)
f[n - 1] = l[n - 1] * x
maksi = pref[n - 1]
for i in range(1, n):
	j = n - i - 1
	maksi = max(maksi, pref[j])
	f[j] = x * l[j] + max(f[j + 1], maksi - pref[j])
wyn = - 100000000000000000000000
for i in range(n):
	wyn = max(wyn, f[i] + b[i] - x * l[i])
mini = 0
wyn1 = -100000000000000000000000
for i in range(n):
	mini = min(mini, pref[i])
	wyn1 = max(wyn1, pref[i] - mini)
print(max(wyn, wyn1))

def main():
    n, x = list(map(int, input().split()))
    a = list(map(int, input().split()))

    dp = [[0, 0, 0] for _ in range(n)]
    dp[0][0] = max(0, a[0])
    dp[0][1] = max(0, x * a[0])
    answer = max(dp[0])

    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][0] + a[i], a[i])
        dp[i][1] = max(dp[i - 1][1] + x * a[i], x * a[i],
                       dp[i - 1][0] + x * a[i])
        dp[i][2] = max(dp[i - 1][2] + a[i], dp[i - 1][1] + a[i])
        answer = max(answer, *dp[i])

    print(answer)


def __starting_point():
    main()

__starting_point()

n,x=list(map(int,input().split())) 
a=list(map(int,input().split())) 
dp=[[0 for i in range(3)] for j in range(n+1)]
a=[0]+a
#3 dps lagenge >:|)
res=0
for i in range(1,n+1):
    dp[i][0]= max(0,dp[i-1][0]+a[i],a[i]) #current le ya na le
    dp[i][1]=max(0,dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x,a[i]*x) #check and see which gives the best ans
    dp[i][2]= max(0,a[i],dp[i-1][0]+a[i],dp[i-1][1]+a[i],dp[i-1][2]+a[i]) #main dp
    res=max(res,dp[i][0],dp[i][1],dp[i][2])
    #print(dp)
print(res)



n,x=map(int, input().split())
A=list(map(int,input().split()))
DP=[[0]*3 for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    DP[i][0]=max(DP[i-1][0]+A[i-1],A[i-1])
    DP[i][1]=max(DP[i-1][0]+A[i-1]*x,DP[i-1][1]+A[i-1]*x,A[i-1]*x)
    DP[i][2]=max(DP[i-1][1]+A[i-1],DP[i-1][2]+A[i-1],A[i-1])
    ans=max(ans,max(DP[i]))
print(ans)

d1, d2, d3, d4 = 0, 0, 0, 0
e1, e2, e3, e4 = 0, 0, 0, 0
n, x = map(int, input().split())
A = list(map(int, input().split())) + [0]
for a in A:
    e1 = max(a, d1 + a)
    e2 = max(x*a, d1 + x*a, d2 + x*a)
    e3 = max(e1, d2 + a, d3 + a)
    e4 = max(d1, d2, d3, d4, a)
    d1, d2, d3, d4 = e1, e2, e3, e4
print(d4)

def solve():
    N, X = map(int, input().split())
    A = [int(k) for k in input().split()]
    
    ans = 0
    cur_max1 = 0
    cur_max2 = 0
    cur_max3 = 0
    
    for a in A:
        #max sum subarray
        '''
        if A[i] > cur_max + A[i]:
            cur_max = A[i]
        else:
            cur_max += A[i]'''
        
        # normal max sum subarray
        cur_max1 = max(a, cur_max1 + a)
        # multiply by X
        cur_max2 = max(a*X, a*X + cur_max2, cur_max1)
        # max sum subarray with previous sum multiplied by X
        cur_max3 = max(a, cur_max3 + a, cur_max2)
            
        ans = max(ans, cur_max1, cur_max2, cur_max3, 0)
    
    print (ans)
    
def __starting_point():  
    solve()
__starting_point()

def printarr(dp):
    for i in dp:
        print(*i)

n,m=list(map(int,input().split()))
a=[0] + list(map(int,input().split()))
dp=[[0 ,0 ,0] for i in range(n+1)]
ma=-1
for i in range(1,n+1):
    dp[i][0]=max(dp[i-1][0] + a[i],0)
    dp[i][1]=max(dp[i-1][1] + a[i]*m, dp[i-1][0] + a[i]*m)
    dp[i][2]=max(dp[i-1][2] + a[i] ,a[i] + dp[i-1][1])
    ma=max(dp[i][0],dp[i][1],dp[i][2],ma)
# printarr(dp)    
print(ma)    


def find(A, x):
    maxi, c1, c2, c3 = 0, 0, 0, 0
    for i in range(0, len(A)):
        c1 = max([c1 + A[i], 0])
        c2 = max([c1, c2 + A[i] * x])
        c3 = max([c2, c3 + A[i]])
        maxi = max([maxi, c1, c2, c3])
    return maxi

inp = lambda cast=int: list(map(cast, input().split()))
n, x = inp()
A = [0] + inp()
print(find(A, x))

def find(A, x):
    maxi, c1, c2, c3 = 0, 0, 0, 0
    for i in range(0, len(A)):
        c11 = max([c1, 0]) + A[i]
        c22 = max([c1, c2, 0]) + A[i] * x
        c33 = max([c2, c3, 0]) + A[i]
        c1, c2, c3 = c11, c22, c33
        maxi = max([maxi, c1, c2, c3])
    return maxi

inp = lambda cast=int: list(map(cast, input().split()))
n, x = inp()
A = [0] + inp()
print(find(A, x))

def solve():
    n, x = list(map(int, input().split()))
    a = [0] + list(map(int, input().split()))
    max_val = 0
    dp1 = [0] * (n + 1)
    for i in range(1, n + 1):
        dp1[i] = max(dp1[i-1] + a[i], a[i])
        max_val = max(max_val, dp1[i])

    dp2 = [0] * (n + 1)
    for i in range(1, n + 1):
        dp2[i] = max(dp1[i-1] + a[i] * x, dp2[i-1] + a[i] * x, a[i] * x)
        max_val = max(max_val, dp2[i])

    dp3 = [0] * (n + 1)
    for i in range(1, n + 1):
        dp3[i] = max(dp2[i-1] + a[i], dp3[i-1] + a[i], a[i])
        max_val = max(max_val, dp3[i])

    print(max_val)

solve()


import sys
input = sys.stdin.readline

n,x=list(map(int,input().split()))
A=list(map(int,input().split()))

SUM=[0]

for a in A:
    SUM.append(SUM[-1]+a)

MAXLIST=[SUM[0]]
MINLIST=[SUM[0]]

for i in range(1,n+1):
    MAXLIST.append(max(MAXLIST[-1],SUM[i]))
    MINLIST.append(min(MINLIST[-1],SUM[i]))

MAXLIST_INV=[SUM[-1]]
MINLIST_INV=[SUM[-1]]

for i in range(n-1,-1,-1):
    MAXLIST_INV.append(max(MAXLIST_INV[-1],SUM[i]))
    MINLIST_INV.append(min(MINLIST_INV[-1],SUM[i]))

MAXLIST_INV=MAXLIST_INV[::-1]
MINLIST_INV=MINLIST_INV[::-1]


if x>0:
    
    ANS=0
   
    for i in range(n+1):
        base=SUM[i]
        MINUS=MINLIST[i]

        ANS=max(ANS,(base-MINUS)*x)

    print(ANS)

else:

    ANS=0
    MAX=0
    MIN=0
    MINUS=0
    NOWMINUS=0
   
    for i in range(n+1):
        base=SUM[i]
        PLUS=MAXLIST_INV[i]#getvalues(i,n+2,0,0,seg_el)

        ANS=max(ANS,NOWMINUS+PLUS-base+base*x)

        MIN=min(MIN,SUM[i])
        
        if NOWMINUS<=SUM[i]-MIN+SUM[i]*(-x):
            NOWMINUS=SUM[i]-MIN+SUM[i]*(-x)
            MAX=SUM[i]


    print(ANS)  


import sys
input = sys.stdin.readline

n,x=list(map(int,input().split()))
A=list(map(int,input().split()))

DP0=[0]*(n+1)
DP1=[0]*(n+1)
DP2=[0]*(n+1)

for i in range(n):
    DP0[i]=max(DP0[i-1]+A[i],A[i],0)
    DP1[i]=max(DP0[i-1]+A[i]*x,DP1[i-1]+A[i]*x,DP0[i])
    DP2[i]=max(DP2[i-1]+A[i],DP1[i-1]+A[i],DP1[i])

print(max(DP2))



n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
def factiry(arr,mul):
    curMax,mulMax,gloMax,cur = 0,0,0,0
    for i in range(n):
        curMax=max(arr[i]+curMax,0)
        mulMax = max(mulMax+(arr[i]*mul),curMax)
        cur = max(cur+arr[i],mulMax)
        gloMax = max(gloMax,cur)
    return (gloMax)
total = factiry(a,m)
print(total)




n, x = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
dp = [[-10**18 for i in range(5)] for j in range(len(A))]

for i in range(n-1, -1, -1):
    if 1:
        nxt = [0, 0, 0, 0, 0]
        if i!=n-1:
            nxt = dp[i+1]
        coeff = [0, 1, x, 1, 0]
        for j in range(5):
            for xx in range(j, len(coeff)):
                dp[i][j] = max(dp[i][j], coeff[xx]*A[i] + nxt[xx])
        
        

print(max(dp[0]))


# AC
import sys
from math import gcd


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = sys.stdin.readline().split()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_int(self):
        return int(next(self))

    def solve(self):
        n = self.next_int()
        k = self.next_int()
        x = [self.next_int() for _ in range(0, n)]
        ans = 0
        dp = (0, 0, 0)
        for xx in x:
            d0 = max(0, dp[0]) + xx
            d1 = max(0, dp[0], dp[1]) + xx * k
            d2 = max(0, dp[0], dp[1], dp[2]) + xx
            ans = max(ans, d0, d1, d2)
            dp = (d0, d1, d2)
        print(ans)


def __starting_point():
    Main().solve()

__starting_point()