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: HARD
Tags: Greedy algorithms

Complete search

Dynamic programming

Divide and conquer

Data structures
Skill types: Dynamic programming

Data structures

Complete search

Greedy algorithms

Starter code:

Solutions:
def printarr(dp):
	for i in dp:
		print(*i)
(n, m) = 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)
print(ma)


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

def solve(n, x, a):
	s = [a[0]] * n
	left = [max(a[0], 0)] * n
	right = [max(a[-1], 0)] * n
	for i in range(1, n):
		left[i] = max(left[i - 1] + a[i], a[i], 0)
		s[i] = s[i - 1] + a[i]
	for i in range(n - 2, -1, -1):
		right[i] = max(right[i + 1] + a[i], a[i], 0)
	res = c = 0
	for r in range(n):
		if r < n - 1:
			res = max(res, right[r + 1] + x * s[r] + c)
		else:
			res = max(res, x * s[r] + c)
		res = max(res, left[r])
		c = max(c, left[r] - x * s[r])
	return res
print(solve(n, x, a))


(n, x) = 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)


import sys, math
from collections import defaultdict, deque
input = sys.stdin.readline
(n, x) = map(int, input().split())
l = list(map(int, input().split()))
dp = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(len(l))]
dp[0][0][0] = l[0]
dp[0][1][0] = l[0]
dp[0][1][1] = x * l[0]
ans = max(l[0], l[0] * x, 0)
for i in range(1, n):
	dp[i][0][0] = max(l[i], l[i] + max(dp[i - 1][0][0], dp[i - 1][1][1]))
	dp[i][1][0] = max(l[i], l[i] + dp[i - 1][1][0])
	dp[i][1][1] = max(l[i] * x, l[i] * x + max(dp[i - 1][1][1], dp[i - 1][1][0]))
	ans = max(ans, dp[i][0][0], dp[i][1][0], dp[i][1][1])
print(ans)


def solve(N, X, A):
	ans = best1 = best2 = best3 = 0
	for a in A:
		best3 = max(0, a, best1 + a, best2 + a, best3 + a)
		best2 = max(0, X * a, best1 + X * a, best2 + X * a)
		best1 = max(0, a, best1 + a)
		ans = max(ans, best1, best2, best3)
	return ans
(N, X) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
print(solve(N, X, A))


(N, X) = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] * 3 for i in range(N + 1)]
ans = 0
for i in range(N):
	dp[i + 1][0] = max(0, dp[i][0] + a[i])
	dp[i + 1][1] = max(0, dp[i][1] + a[i] * X, dp[i][0] + a[i] * X)
	dp[i + 1][2] = max(0, dp[i][1] + a[i], dp[i][2] + a[i])
	ans = max(ans, dp[i + 1][0], dp[i + 1][1], dp[i + 1][2])
print(ans)


def beauty(arr, x):
	d = [[[-float('inf') for k in range(3)] for j in range(3)] for i in range(len(arr) + 1)]
	d[0][0][0] = 0
	ans = 0
	for i in range(len(arr)):
		for j in range(3):
			for k in range(3):
				if k < 2:
					d[i][j][k + 1] = max(d[i][j][k + 1], d[i][j][k])
				if j < 2:
					d[i][j + 1][k] = max(d[i][j + 1][k], d[i][j][k])
				d[i + 1][j][k] = max(d[i + 1][j][k], d[i][j][k] + [0, arr[i]][j == 1] * [1, x][k == 1])
				ans = max(ans, d[i + 1][j][k])
	return ans
(a, b) = map(int, input().strip().split())
lst = list(map(int, input().strip().split()))
print(beauty(lst, b))


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))


import sys
input = sys.stdin.readline
(n, x) = map(int, input().split())
a = [int(x) for x in input().split()]
dp = [[0, 0, 0, 0] for i in range(n)]
for i in range(n):
	dp[i][0] = max(a[i], dp[i - 1][0] + a[i])
	dp[i][1] = max(a[i] * x, dp[i - 1][0] + a[i] * x)
	dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + a[i] * x
	dp[i][3] = max(dp[i - 1][3], max(dp[i - 1][2], dp[i - 1][1])) + a[i]
maxi = 0
for i in range(n):
	maxi = max(maxi, max(dp[i]))
print(maxi if n > 1 else max(max(a[0] * x, a[0]), 0))


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
b = [[0] * 3 for i in range(n)]
for i in range(n):
	if i == 0:
		b[i][0] = max(a[i], 0)
		b[i][1] = a[i] * x
		b[i][2] = max(b[i][1], a[i])
	else:
		b[i][0] = max(b[i - 1][0] + a[i], 0)
		b[i][1] = max(b[i - 1][1] + a[i] * x, b[i - 1][0] + a[i] * x, 0)
		b[i][2] = max(b[i][1], b[i - 1][2] + a[i])
print(max(max(b, key=lambda x: max(x))))


(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]))


(N, X) = map(int, input().split())
ans = 0
for (i, x) in enumerate(map(int, input().split())):
	if i == 0:
		dp = (max(0, x), max(0, x * X), max(0, x))
	else:
		dp = (max(0, dp[0] + x), max(0, dp[1] + x * X, dp[0] + x * X), max(0, dp[2] + x, dp[1] + x))
	ans = max(ans, dp[0], dp[1], dp[2])
print(ans)


(n, m) = map(int, input().split())
lis = list(map(int, input().split()))
pref = suff = main = ans = 0
for i in lis:
	pref = max(pref + i, 0)
	suff = max(suff + i * m, pref)
	main = max(main + i, suff)
	ans = max(ans, main)
print(ans)


def main():
	(n, x) = 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)
main()


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))


(n, m) = map(int, input().split())
dp = [[[-9487948794879487] * 3 for j in range(3)] for i in range(n + 1)]
nums = list(map(int, input().split()))
dp[0][0][0] = 0
dp[0][1][0] = 0
for i in range(1, n + 1):
	dp[i][0][0] = dp[i - 1][0][0]
	dp[i][1][0] = max(dp[i - 1][1][0] + nums[i - 1], dp[i - 1][0][0] + nums[i - 1])
	dp[i][2][0] = max(dp[i - 1][2][0], dp[i][1][0])
	dp[i][1][1] = max(dp[i - 1][1][0] + nums[i - 1] * m, dp[i - 1][1][1] + nums[i - 1] * m, nums[i - 1] * m)
	dp[i][1][2] = max(dp[i - 1][1][1] + nums[i - 1], dp[i][1][1], dp[i - 1][1][2] + nums[i - 1])
	dp[i][2][2] = max(dp[i][2][0], dp[i][1][2], dp[i - 1][2][2], dp[i][0][0])
print(dp[n][2][2])


import sys, os
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
m = 998244353

def main():
	(n, x) = read()
	arr = read()
	dp = [[[0] * 2 for i in range(2)] for j in range(n + 1)]
	dp[0][1][0] = arr[0]
	dp[0][1][1] = x * arr[0]
	ans = max(0, arr[0], x * arr[0])
	for i in range(1, n):
		dp[i][0][0] = max(arr[i], arr[i] + max(dp[i - 1][1][1], dp[i - 1][0][0]))
		dp[i][1][0] = max(arr[i], arr[i] + dp[i - 1][1][0])
		dp[i][1][1] = max(arr[i] * x, arr[i] * x + max(dp[i - 1][1][1], dp[i - 1][1][0]))
		ans = max(ans, dp[i][0][0], dp[i][1][0], dp[i][1][1])
	print(ans)
main()


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()


(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)


(n, m) = 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) = 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
res = 0
for i in range(1, n + 1):
	dp[i][0] = max(0, dp[i - 1][0] + a[i], a[i])
	dp[i][1] = max(0, dp[i - 1][0] + a[i] * x, dp[i - 1][1] + a[i] * x, a[i] * x)
	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])
	res = max(res, dp[i][0], dp[i][1], dp[i][2])
print(res)


(n, m) = (int(x) for x in input().split())
multipliers = [1] * 3
multipliers[1] = m
arr = [int(x) for x in input().split()]
dp = [[0 for j in range(3)] for i in range(n + 1)]
for i in range(n):
	for j in range(len(multipliers)):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + arr[i] * multipliers[j])
		if j + 1 < len(multipliers):
			dp[i][j + 1] = max(dp[i][j], dp[i][j + 1])
print(max(map(max, dp)))


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:
		cur_max1 = max(a, cur_max1 + a)
		cur_max2 = max(a * X, a * X + cur_max2, cur_max1)
		cur_max3 = max(a, cur_max3 + a, cur_max2)
		ans = max(ans, cur_max1, cur_max2, cur_max3, 0)
	print(ans)
solve()


(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)


(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)


(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)


import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))

def main():
	(n, x) = get_list()
	li = get_list()
	u_before = [0] * n
	not_u = [0] * n
	being_u = [0] * n
	(u_before[0], not_u[0], being_u[0]) = (li[0], li[0], li[0] * x)
	for i in range(1, n):
		u_before[i] = max(li[i], li[i] + u_before[i - 1], li[i] + being_u[i - 1])
		not_u[i] = max(li[i], li[i] + not_u[i - 1])
		being_u[i] = max(li[i] * x, li[i] * x + not_u[i - 1], li[i] * x + being_u[i - 1])
	print(max(max(u_before), max(not_u), max(being_u), 0))
main()
print(*out, sep='\n')


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


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, X, A):
	dp = [[[float('-inf') for _ in range(3)] for _ in range(3)] for _ in range(N + 1)]
	dp[0][0][0] = 0
	for i in range(N + 1):
		for j in range(3):
			for k in range(3):
				if k < 2:
					dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
				if j < 2:
					dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
				if i < N:
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (A[i] if j == 1 else 0) * (X if k == 1 else 1))
	return dp[N][2][2]
(N, X) = map(int, input().split())
A = [int(x) for x in input().split()]
print(solve(N, X, A))


l = input().split()
n = int(l[0])
x = int(l[1])
l = input().split()
li = [int(i) for i in l]
right = [0 for i in range(n)]
left = [0 for i in range(n)]
pref = [0 for i in range(n)]
pref[0] = li[0]
for i in range(1, n):
	left[i] = max(0, li[i - 1] + left[i - 1])
	pref[i] = pref[i - 1] + li[i]
for i in range(n - 2, -1, -1):
	right[i] = max(0, li[i + 1] + right[i + 1])
maxleft = 0
ans = 0
for i in range(n):
	if i == 0:
		maxleft = max(maxleft, left[i])
	else:
		maxleft = max(maxleft, left[i] - x * pref[i - 1])
	ans = max(ans, right[i] + x * pref[i] + maxleft)
dp = [0 for i in range(n)]
dp[0] = li[0]
for i in range(1, n):
	dp[i] = max(dp[i - 1] + li[i], li[i])
print(max(max(dp), ans))


from math import inf

def main():
	nx = input().split(' ')
	(n, x) = (int(nx[0]), int(nx[1]))
	a = input().split(' ')
	a = [int(x) for x in a]
	dp = [[[-inf for i in range(3)] for j in range(3)] for k in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n + 1):
		for j in range(3):
			for k in range(3):
				if k < 2:
					dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
				if j < 2:
					dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
				if i < n:
					if j == 1:
						j_check = a[i]
					else:
						j_check = 0
					if k == 1:
						k_check = x
					else:
						k_check = 1
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + j_check * k_check)
	print(dp[n][2][2])
main()


import sys
import math as mt
import bisect
t = 1

def solve():
	suma = dp[0][3]
	for i in range(1, n):
		dp[i][0] = 0
		dp[i][1] = l[i] + dp[i - 1][1]
		dp[i][2] = x * l[i] + dp[i - 1][2]
		dp[i][3] = l[i] + dp[i - 1][3]
		for j in range(1, 4):
			dp[i][j] = max(dp[i][j - 1], dp[i][j])
		suma = max(dp[i][3], suma)
	return suma
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	dp = [[0 for j in range(4)] for i in range(n)]
	dp[0][0] = 0
	dp[0][1] = l[0]
	dp[0][2] = x * l[0]
	dp[0][3] = l[0]
	for j in range(1, 4):
		dp[0][j] = max(dp[0][j], dp[0][j - 1])
	print(solve())


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def fn(pos, state):
	if pos < 0:
		return 0
	if state == 2:
		ans = max(a[pos], x * a[pos] + fn(pos - 1, 1), a[pos] + fn(pos - 1, 2))
	elif state == 1:
		ans = max(a[pos], x * a[pos] + fn(pos - 1, 1), a[pos] + fn(pos - 1, 0))
	else:
		ans = max(a[pos], a[pos] + fn(pos - 1, 0))
	return max(0, ans)
for _ in range(1):
	(n, x) = lst()
	a = lst()
	dp = [[0 for i in range(3)] for i in range(1 + n)]
	for i in range(1, n + 1):
		for j in range(3):
			if j == 0:
				dp[i][j] = max(0, a[i - 1], a[i - 1] + dp[i - 1][0])
			elif j == 1:
				dp[i][j] = max(0, a[i - 1], x * a[i - 1] + dp[i - 1][1], a[i - 1] + dp[i - 1][0])
			else:
				dp[i][j] = max(0, x * a[i - 1] + dp[i - 1][1], a[i - 1] + dp[i - 1][2])
	ans = 0
	for i in range(1, 1 + n):
		ans = max(ans, dp[i][2])
	print(ans)


def main():
	print = out.append
	(n, x) = get_list()
	li = get_list()
	ans = best1 = best2 = best3 = 0
	for a in li:
		best3 = max(0, best1 + a, best2 + a, best3 + a)
		best2 = max(0, best1 + x * a, best2 + x * a)
		best1 = max(0, best1 + a)
		ans = max(ans, best1, best2, best3)
	print(ans)
import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
main()
print(*out, sep='\n')


(n, x) = map(int, input().split())
l = list(map(int, input().split()))
(plus_cunt, cross_cunt, cunt, result) = (0, 0, 0, 0)
for ele in l:
	plus_cunt = max(plus_cunt + ele, 0)
	cross_cunt = max(plus_cunt, cross_cunt + ele * x)
	cunt = max(cunt + ele, cross_cunt)
	result = max(result, cunt)
print(result)


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
inf = -2 ** 64
dp = [[[inf for _ in range(3)] for _ in range(3)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n + 1):
	for j in range(3):
		for k in range(3):
			if k < 2:
				dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
			if j < 2:
				dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
			if i < n:
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (a[i] if j == 1 else 0) * int(x if k == 1 else 1))
print(dp[n][2][2])


import sys
from functools import reduce
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(int(10000000.0))
intinput = lambda : list(map(int, input().split()))

def f(hi, t):
	global a, x, M, V
	if V[hi][t] == 1:
		return M[hi][t]
	if hi == 0:
		ans = 0
	elif t == 0:
		ans = max(f(hi - 1, 0) + a[hi - 1], 0)
	elif t == 1:
		ans = max(f(hi - 1, 0) + x * a[hi - 1], f(hi - 1, 1) + x * a[hi - 1])
	elif t == 2:
		ans = max(f(hi - 1, 1) + a[hi - 1], f(hi - 1, 2) + a[hi - 1])
	V[hi][t] = 1
	M[hi][t] = ans
	return ans

def main():
	global a, x, M, V
	(n, x) = intinput()
	a = intinput()
	M = [[0, 0, 0] for hi in range(n + 1)]
	V = [[0, 0, 0] for hi in range(n + 1)]
	ans = max((f(hi, t) for t in range(3) for hi in range(n + 1)))
	print(ans)
	return
while 1:
	try:
		main()
	except EOFError:
		break


(N, X) = 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])


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()


def go():
	(n, x) = map(int, input().split(' '))
	a = [int(i) for i in input().split(' ')]
	cur1 = cur2 = cur = maximum = 0
	for i in range(len(a)):
		cur1 = max(0, cur1 + a[i])
		cur2 = max(cur1, cur2 + x * a[i])
		cur = max(cur + a[i], cur2)
		maximum = max(maximum, cur)
	return maximum
print(go())


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
kq = pre = mid = suf = 0
for i in a:
	pre = max(pre + i, 0)
	mid = max(mid + i * x, pre)
	suf = max(suf + i, mid)
	kq = max(kq, suf)
print(kq)


(n, x) = map(int, input().split())
a = [int(i) for i in input().split()]
a.insert(0, 0)
pref = [0]
dp = [[0, 0, 0] for _ in range(n + 1)]
for i in range(1, n + 1):
	dp[i][0] = max(0, dp[i - 1][0] + a[i])
	dp[i][1] = max(0, dp[i - 1][0] + x * a[i], dp[i - 1][1] + x * a[i])
	dp[i][2] = max(0, dp[i][0], dp[i][1], dp[i - 1][2] + a[i])
maxa = 0
for i in range(len(dp)):
	maxa = max(maxa, dp[i][2])
print(maxa)


(n, k) = map(int, input().split())
l = [*map(int, input().split())]
dp = [[0] * 3 for i in range(n)]
for i in range(n):
	for j in range(3):
		dp[i][j] = float('inf')
ans = 0
for i in range(n):
	if i == 0:
		dp[i][0] = max(l[i], 0)
		dp[i][1] = max(l[i] * k, 0)
		dp[i][2] = max(l[i], 0)
	else:
		dp[i][0] = max(dp[i - 1][0] + l[i], 0)
		dp[i][1] = max(max(dp[i - 1][0], dp[i - 1][1]) + l[i] * k, 0)
		dp[i][2] = max(max(dp[i - 1][1], dp[i - 1][2]) + l[i], 0)
	ans = max(ans, max(dp[i][0], dp[i][1], dp[i][2]))
print(ans)


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

def DP_Beautiful_array(v, n, x):
	dp = [[0] * 3 for i in range(n)]
	dp[0][0] = v[0]
	dp[0][1] = x * v[0]
	answer = max(0, max(v[0], x * v[0]))
	for i in range(1, n, 1):
		dp[i][0] = max(v[i], v[i] + dp[i - 1][0])
		dp[i][1] = max(x * v[i], x * v[i] + max(dp[i - 1][1], dp[i - 1][0]))
		dp[i][2] = max(v[i], v[i] + max(dp[i - 1][1], dp[i - 1][2]))
		answer = max(answer, max(dp[i][0], max(dp[i][1], dp[i][2])))
	print(answer)
DP_Beautiful_array(v, n, x)


import sys
input = sys.stdin.readline
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 18
dp = [[[-INF] * 3 for i in range(3)] for j in range(n + 1)]
dp[0][0][0] = 0
for i in range(n + 1):
	for j in range(3):
		for k in range(3):
			if k < 2:
				dp[i][j][k + 1] = max(dp[i][j][k], dp[i][j][k + 1])
			if j < 2:
				dp[i][j + 1][k] = max(dp[i][j][k], dp[i][j + 1][k])
			if i < n:
				if k == 1:
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + a[i] * (j == 1) * x)
				else:
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + a[i] * (j == 1) * 1)
print(dp[n][2][2])


(n, m) = input().split(' ')
n = int(n)
m = int(m)
arr = input().split(' ')
arr = [0] + [int(x) for x in arr]
dp = [[0] * (len(arr) + 1) for i in range(3)]
ans = 0
for i in range(1, len(arr)):
	dp[0][i] = max(0, dp[0][i - 1]) + arr[i]
	dp[1][i] = max(dp[0][i - 1], max(0, dp[1][i - 1])) + arr[i] * m
	dp[2][i] = max(max(dp[0][i - 1], dp[1][i - 1]), max(0, dp[2][i - 1])) + arr[i]
	ans = max(max(max(dp[0][i], dp[1][i]), dp[2][i]), ans)
print(ans)


(n, x) = [int(x) for x in input().split()]
data = [int(x) for x in input().split()]
dp = [[0 for _ in range(3)] for _ in range(n + 1)]
for (i, v) in enumerate(data):
	i += 1
	dp[i][0] = max(dp[i - 1][0] + v, v)
	dp[i][1] = max(dp[i - 1][0] + v * x, v * x, dp[i - 1][1] + v * x)
	dp[i][2] = max(dp[i - 1][1] + v, dp[i - 1][2] + v)
print(max([x for d in dp for x in d]))


(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)


import sys
from bisect import *
pl = 1
from copy import *
if pl:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('outpt.txt', 'w')

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())
(n, k) = mi()
a = li()
maxi = 0
dp = [[0, 0, 0] for i in range(n + 2)]
for i in range(n):
	if i == 0:
		dp[i][0] = max([dp[i - 1][0] + a[i], a[i]])
		dp[i][1] = a[i] * k
		dp[i][2] = -10 ** 18
	else:
		dp[i][0] = max([dp[i - 1][0] + a[i], a[i]])
		dp[i][1] = max([dp[i - 1][1] + a[i] * k, dp[i - 1][0] + a[i] * k, a[i] * k])
		dp[i][2] = max([dp[i - 1][1] + a[i], dp[i - 1][2] + a[i], a[i]])
	maxi = max(maxi, max(dp[i]))
print(maxi)


(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])


(n, x) = map(int, input().split())
lis = list(map(int, input().split()))
dp = dict()
mx = mx = float('-inf')
dp[0, 1, 0] = lis[0]
dp[0, 1, 1] = x * lis[0]
dp[0, 0, 0] = 0
mx = max(mx, max(dp[0, 1, 0], dp[0, 1, 1]))
for i in range(1, n):
	dp[i, 1, 1] = max(x * lis[i], x * lis[i] + max(dp[i - 1, 1, 0], dp[i - 1, 1, 1]))
	dp[i, 1, 0] = max(lis[i], lis[i] + dp[i - 1, 1, 0])
	dp[i, 0, 0] = max(lis[i], lis[i] + max(dp[i - 1, 0, 0], dp[i - 1, 1, 1]))
	mx = max(mx, dp[i, 1, 1], dp[i, 1, 0], dp[i, 0, 0])
print(0 if mx < 0 else mx)


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()


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]
		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

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]
INF = 1 << 64

def main():
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	A = [0] + a.copy()
	revA = [0] + a.copy()[::-1]
	b = [-INF] * n
	revb = [-INF] * n
	ans = 0
	for i in range(1, n + 1):
		A[i] += A[i - 1]
		revA[i] += revA[i - 1]
	for i in range(1, n + 1):
		ans = max(A[i] - A[i - 1], ans)
		b[i - 1] = max(A[i] - A[i - 1], 0)
		revb[i - 1] = max(revA[i] - revA[i - 1], 0)
		A[i] = min(A[i], A[i - 1])
		revA[i] = min(revA[i], revA[i - 1])
	dp0 = [-INF] * n
	for i in range(n):
		if i > 0:
			dp0[i] = max(dp0[i - 1] + x * a[i], b[i - 1] + x * a[i])
		else:
			dp0[i] = x * a[i]
	dp1 = [-INF] * n
	for i in range(n):
		if i > 0:
			dp1[i] = max(dp1[i - 1] + x * a[n - 1 - i], revb[i - 1] + x * a[n - 1 - i])
		else:
			dp1[i] = x * a[n - 1 - i]
	for i in range(n):
		ans = max(ans, dp0[i] + dp1[n - 1 - i] - x * a[i])
	print(ans)
	return 0
main()


(n, x) = list(map(int, input().split()))
a = list(map(int, input().split()))
a_mult_x = [0] * n
for i in range(n):
	a_mult_x[i] = a[i] * x
dp = []
dp.append([0] * n)
dp.append([0] * n)
dp.append([0] * n)
if a[0] > 0:
	dp[0][0] = a[0]
	dp[2][0] = a[0]
if a_mult_x[0] > 0:
	dp[1][0] = a_mult_x[0]
for i in range(1, n):
	dp[0][i] = max(0, dp[0][i - 1]) + a[i]
	dp[1][i] = max(0, dp[0][i - 1], dp[1][i - 1]) + a_mult_x[i]
	dp[2][i] = max(0, dp[1][i - 1], dp[2][i - 1]) + a[i]
print(max(max(dp[0]), max(dp[1]), max(dp[2])))


IN = input().split()
n = int(IN[0])
x = int(IN[1])
A = input().split()
dp = [0] * 3
for i in range(0, 3):
	dp[i] = [0] * (n + 1)
ans = 0
for i in range(0, n):
	idx = i + 1
	cur = int(A[i])
	dp[0][idx] = max(0, dp[0][idx - 1] + cur)
	dp[1][idx] = max(0, max(dp[0][idx - 1], dp[1][idx - 1]) + cur * x)
	dp[2][idx] = max(0, max(dp[2][idx - 1], dp[1][idx - 1]) + cur)
	for j in range(0, 3):
		ans = max(ans, dp[j][idx])
print(ans)


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
l = [0 for i in range(n + 1)]
r = [0 for i in range(n + 1)]
pre = [a[0]]
for i in range(1, n):
	pre.append(pre[-1] + a[i])
max_ending_here = 0
max_so_far = 0
for i in range(n):
	max_ending_here += a[i]
	if max_ending_here < 0:
		max_ending_here = 0
	l[i] = max_ending_here
max_ending_here = 0
max_so_far = 0
for i in range(n - 1, -1, -1):
	max_ending_here += a[i]
	if max_ending_here < 0:
		max_ending_here = 0
	r[i] = max_ending_here
rans = lans = 0
for i in range(n):
	rans = max(rans, r[i + 1] + pre[i] * x + lans)
	rans = max(rans, l[i])
	lans = max(lans, l[i] - pre[i] * x)
print(rans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
(n, X) = inpl()
a = inpl()
dp = [[0] * (n + 1) for _ in range(5)]
for i in range(n):
	for j in range(5):
		tmp = 0
		if j == 1 or j == 3:
			tmp = a[i]
		elif j == 2:
			tmp = a[i] * X
		for k in range(j + 1):
			dp[j][i + 1] = max(dp[j][i + 1], dp[k][i] + tmp)
res = -INF
for i in range(5):
	res = max(res, dp[i][-1])
print(res)


import sys
input = sys.stdin.readline
(n, x) = 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, x) = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0 for _ in range(n + 1)] for _ in range(3)]
ans = 0
for i in range(n):
	dp[0][i + 1] = max(0, dp[0][i] + a[i])
	dp[1][i + 1] = max(dp[0][i], dp[1][i]) + a[i] * x
	dp[2][i + 1] = max(dp[0][i], dp[1][i], dp[2][i]) + a[i]
	ans = max(ans, dp[0][i + 1], dp[1][i + 1], dp[2][i + 1])
print(ans)


def main():
	(n, x) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ans = a = b = c = 0
	for i in l:
		c = max(0, i, a + i, b + i, c + i)
		b = max(0, i * x, a + i * x, b + i * x)
		a = max(0, i, a + i)
		ans = max(0, ans, a, b, c)
	print(ans)
main()


def maxBeauty():
	dp = [[0 for i in range(3)] for j in range(n)]
	dp[0][0] = max(a[0], 0)
	dp[0][1] = max(a[0] * x, 0)
	dp[0][2] = max(a[0], 0)
	ans = 0
	ans = max([ans, dp[0][0], dp[0][1], dp[0][2]])
	for i in range(1, n):
		dp[i][0] = max(dp[i - 1][0] + a[i], 0)
		dp[i][1] = max(max(dp[i - 1][0], dp[i - 1][1]) + a[i] * x, 0)
		dp[i][2] = max(max(dp[i - 1][1], dp[i - 1][2]) + a[i], 0)
		ans = max([ans, dp[i][0], dp[i][1], dp[i][2]])
	return ans
lin = [int(i) for i in input().split()]
n = lin[0]
x = lin[1]
a = [int(i) for i in input().split()]
print(maxBeauty())