A - A Multiply
Source: atcoder
Difficulty: 300

Problem Statement
You are given an integer sequence of length
N
,
A=(A_1,A_2,\dots,A_N)
, and an integer
C
.
Find the maximum possible sum of the elements in
A
after performing the following operation
at most once
:
Specify integers
l
and
r
such that
1 \le l \le r \le N
, and multiply each of
A_l,A_{l+1},\dots,A_r
by
C
.
Constraints
All input values are integers.
1 \le N \le 3 \times 10^5
-10^6 \le C \le 10^6
-10^6 \le A_i \le 10^6
Input
The input is given from Standard Input in the following format:
N
C
A_1
A_2
\dots
A_N
Output
Print the answer as an integer.
Sample Input 1
5 2
-10 10 20 30 -20
Sample Output 1
90
In this input,
A=(-10,10,20,30,-20), C=2
.
After performing the operation once specifying
l=2
and
r=4
,
A
will be
(-10,20,40,60,-20)
.
Here, the sum of the elements in
A
is
90
, which is the maximum value achievable.
Sample Input 2
5 1000000
-1 -2 -3 -4 -5
Sample Output 2
-15
In this input,
A=(-1,-2,-3,-4,-5), C=1000000
.
Without performing the operation, the sum of the elements in
A
is
-15
, which is the maximum value achievable.
Sample Input 3
9 -1
-9 9 -8 2 -4 4 -3 5 -3
Sample Output 3
13

C++ solution:
/*-------------------------------------------------------------------------⠀
   ⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠎⠀⠀⠀⠀⠘⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠘⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡤⠶⠛⢋⣉⣀⠈⠑⢦⣄⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡤⠖⠋⣁⣤⣶⣿⣿⣿⣿⣷⣦⡀⠀⠀⠒⠶⣶⣤⣀⠀⠸⠀⠀⠀⢐⡒⠒⣲⠖⠉⠀⠀⠀⠉⠉⠙⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠴⠚⢉⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣶⣶⣦⣄⢹⣷⠀⢇⠀⠀⠃⠌⣉⣀⣀⡴⠦⠤⠤⣤⠀⠀⠈⠣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡴⠊⣁⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣇⠈⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢷⡄⠀⠀⠈⢐⡀⠠⠤⣄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠈⠢⢀⣀⣀⠄⠀⠀⠀⠀⠀⣀⣈⠽⠷⠒⠊⠁⠀⠀⢀⠈⠁⢤⣄⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣧⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣏⠀⠀⠀⢄⠀⠀⢀⠜⠁⠀⠀⠀⠙⡧⡀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⣿⣿⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⢻⣆⠀⠀⠀⢳⡔⠁⠀⠀⢠⠀⠀⠈⠙⢗⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⠘⣿⣿⢹⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⡞⠉⠀⠈⠉⠉⠉⠉⡁⢀⡴⠋⠀⠀⠀⢠⠃⠀⠀⠀⡀⠈⢦
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⢸⣿⡗⠶⣿⠒⢿⡟⠸⣿⢹⣿⣿⣿⡟⢿⣿⣿⣷⣄⣀⣀⣣⡤⠄⠒⠒⠦⡀⠀⠘⠿⣄⣀⡀⠀⣰⠃⠀⠀⣀⡜⠁⠀⠈
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⠟⢹⣿⣿⣿⣿⣿⣿⣿⡟⣿⡇⢹⣿⠘⣿⡇⢀⣿⠤⢸⣇⠤⣿⢸⢻⣿⣿⢧⢄⠻⣿⡇⠉⠀⠀⠀⠈⠑⠤⣀⠀⠈⠳⠤⢤⣤⣉⣁⠚⢇⠀⠀⠘⢻⠙⡦⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⡴⠟⠁⠀⢸⣿⣿⣿⣿⣿⡏⣿⣀⣹⡧⠘⢿⠀⠹⡇⠒⠻⡎⠉⢿⠀⠿⢸⢺⡇⠻⡚⠘⠀⡹⠃⠉⢁⠒⡤⠄⠲⠤⣬⣃⡠⠤⢤⡀⠀⠀⠈⢧⠈⢻⢯⣻⠗⠊⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣧⣭⡔⠚⠉⠁⠈⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠈⠁⠀⠿⠆⡴⡥⠖⠉⠀⠀⣸⠀⠀⠀⠈⢹⠈⠙⢦⡹⣦⠀⠀⠈⢧⠈⢦⢩⠉⠒⠶⠖⠒
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⢻⣿⣻⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⢀⣼⠁⠀⠀⠀⠀⢠⡏⠀⠀⠀⠀⠘⡀⠀⠀⠻⢿⠀⠀⠀⠈⣷⠀⢣⢣⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡴⠟⡹⢉⡿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠋⠀⠀⠀⠀⢀⠔⡟⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⢸⣧⠀⠀⠀⠘⣷⡀⢣⢇⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠎⢀⠞⡰⢡⡷⢻⠜⣿⢧⠀⠀⠀⢻⣦⠀⠀⣀⡠⢶⠂⠀⠀⠀⠀⠀⠀⢀⣽⠄⠘⠒⠶⠾⠥⠊⠀⣰⠂⠀⢲⡄⠀⠘⠷⢄⣠⡘⠹⣦⠀⠀⠀⠹⣧⠀⠻⡆⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡠⡪⠃⡰⢃⠎⢀⠟⢀⠎⠀⠀⠘⣆⠀⠀⠘⣿⠻⡉⠀⠀⢸⠀⠀⠀⠀⠀⠀⡰⡟⡇⠀⠀⠀⠀⠀⠀⠀⠀⡀⢹⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⢿⠀⠀⠀⠀⢻⣧⠀⠁⠀⠀
⠀⠀⠀⠀⠀⠀⡴⡑⢁⡴⢣⡢⢢⠟⠠⠋⠀⠀⠀⠀⡟⣦⡀⠀⠈⠀⠙⢆⣀⡟⠀⠀⠀⠀⣠⢊⡔⣧⡇⠀⠀⠀⠀⠀⠀⠀⣠⣇⡉⠉⣟⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠈⣿⡆⠀⠀⠀
⠀⠀⠀⠀⠀⡼⢰⡁⠬⠐⠛⠒⠛⠒⠀⠀⠀⠀⠀⡜⠀⠘⣏⠢⣀⠀⠀⠀⠁⠀⠀⠀⣠⠚⣠⢯⠀⠸⣷⡀⠀⠀⠀⠀⠀⠀⠉⠀⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⣠⡿⠶⠌⠉⠑⠒⠺⣿⡀⠀⠀
⠀⠀⠀⠀⣸⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡡⢪⠄⠹⡦⣏⠳⣤⣀⣀⣠⣴⡾⣷⢰⠃⢸⡰⠀⠈⠉⢗⠶⠦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠖⡺⠁⠀⠀⠀⠀⠀⠀⠀⢻⡧⠀⠀
⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⢼⡱⣡⡇⠀⢹⡌⣦⢹⢫⡏⠙⠙⡀⣿⠃⠁⢸⡇⠀⡀⠀⠈⢻⡄⠀⠀⠀⢀⣶⣶⣶⣶⣶⣦⣀⣀⣠⣴⡁⠀⠀⠀⠀⠀⠀⠀⠀⢸⡀⠀⠀
⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠾⣏⠼⠀⠀⠀⢳⡘⢿⠾⠷⣼⠀⠃⠋⠀⠀⣸⡷⡫⠀⠀⠀⢹⣿⣦⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀
⠀⠀⠀⠈⡷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡔⢇⠀⡇⠀⠀⢸⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⢊⠔⠀⠀⢀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⣆⠀
⠀⠀⠀⢰⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢄⠸⣄⠀⢸⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠒⠁⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⢈⣄⠦⠔⢋⡦⠎⠀⠘⢷
⠀⠀⠀⢸⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠓⠬⣷⡜⠀⢿⡀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⢀⠨⠖⠋⠁⠀⠀⠀⠀⠀
⠀⠀⠀⠈⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠺⣿⣤⣤⣤⣀⣠⣴⢴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠘⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡠⠐⠒⠈⠉⠉⠉⠉⠉⠉⠙⠾⢟⠁⠀⡠⠂⡀⠑⠪⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣆⠀⠀⠀⠀⠀⠀⠀⠀⣀
⠀⠀⠀⠀⠀⠘⣦⡀⠀⠀⠀⠀⠀⢠⢫⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⡔⠁⡰⠁⠀⡰⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⢀⣀⣠⣤⣶⡾⠿⠛
⠀⠀⠀⠀⣠⣾⣿⣷⣄⠀⠀⠀⠀⡌⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠎⠑⣔⠁⠀⡰⠁⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⡿⠿⠛⠿⠋⠁⠀⠀⠀⠀
⠀⠀⠀⣴⣿⣿⣿⣿⣿⣷⣄⢄⠀⣇⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠜⠈⠑⣴⠁⠀⠀⠀⠀⠀⠈⠣⣄⡈⠉⠙⠻⢿⡿⠿⠿⠛⠻⢿⣿⣿⣫⠟⡍⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠐⠢⠄⣀⠀⠀⠀⠀⠈⠉⠁⠀⠀⠘⠛⠋⠑⣤⠊⢀⣔⡫⠚⠠⡸⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠀⠉⠉⠀⠀⠀⠀⠀⠀⠙⠋⠉⠁⠀⠀⠀⠀⠈⢿⡄⠀⠀⠀⠀⠀⠀⠀⠀
⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀
⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡄⣸⠇⠀⠀⠀⠀⠀⠀⠀
                            AUTHOR:ANUSH2010
---------------------------------------------------------------------------*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define jaja cout<<"Yes"
#define nein cout<<"No"
#define r0 return
#define endl '\n'
#define pb push_back
#define pf push_front
#define all(v) (v).begin(),(v).end()
#define me cout<<"-1"
#define vll vector <ll>
#define vld vector <ld>
#define vs vector <string>
#define vf vector <float>
#define vc vector <char>
#define vi vector <int>
#define vb vector <bool>
#define se second()
#define fi first()
bool prime(int n)
{
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}
ll binpow(ll x ,ll n,ll mod)
{
    ll ans=1;
    while(n>0)
    {
        if(n%2==0)
        {
            n--;
            ans=ans*x%mod;
        }
        else
        {
            n/=2;
            x=x*x%mod;
        }
    }
    return ans;
}
const int N=2e5+7;
void solve()
{
   ll i,j,pol=0,col=0,sum=0,pum=0,mx=0,mn=1e18;
   unordered_map<ll,ll>mp;
   unordered_map<char,ll>mp2;
   int n,c;
   cin>>n>>c;
   vi a(n);
   for(i=0;i<n;i++)
   {
       cin>>a[i];
       sum+=a[i];
   }
   if(c>=1)
   {
       ll d=0;
       ll r=0;
       for(i=0;i<n;i++)
       {
           r+=a[i];
           mx=min(mx,r);
           d=max(d,r-mx);
       }
       cout<<(c-1)*d+sum;
       r0;
   }
   else
   {
       ll d=0;
       ll r=0;
       for(i=0;i<n;i++)
       {
           r+=a[i];
           mx=max(mx,r);
           d=min(d,r-mx);
       }
       cout<<(c-1)*d+sum;
   }
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int test=1;
    //cin>>test;
    while(test--)
    {
        solve();
        cout<<endl;
    }
}
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⣎⠢⡀⠀⣀⠤⣲⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢉⣙⣫⡴⠶⠚⠀⠈⠒⠣⢾⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⣩⠵⠋⠔⣒⠨⠍⠁⠀⠀⠀⠩⢭⣛⣒⡂⠤⠀⠀⠀⢀⣀⢀⣤⣤⣀⣀⣴⣶⣄⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠠⠤⠴⣿⢷⡞⡰⠀⡄⠀⢠⣢⡄⢠⢀⢀⣠⢫⡢⣀⠀⠀⣠⣪⣵⣿⣿⣿⣿⣿⣝⣿⣿⡿⢀⣀⣀⡀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠴⠾⣞⡼⣷⡇⡜⣠⣰⠕⡹⢀⢼⡸⣾⢸⠢⣙⢄⠀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣍⠁⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣰⣿⣾⢾⣜⢴⣿⣿⣦⣣⣾⣾⣷⣿⣼⠀⠀⠁⠀⣻⠏⠋⠁⠁⠁⢹⣿⣿⣿⣿⣿⣏⠛⠏⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠉⠀⠉⠈⣿⣏⠘⢿⡿⠏⠉⠹⣿⡿⠻⣏⠀⠀⠀⠀⠹⡔⠒⠀⠀⠐⢹⣟⡉⠈⡿⡝⣹⠃⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣆⠀⠀⠠⡤⡀⠀⢀⡴⠅⠀⠀⠀⠀⠀⡗⠒⠲⠀⠀ ⢺⡏⠀⠀⢡⣿⠋⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣤⣄⣈⠉⢀⣖⠉⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⢀⣀⠈⠇⠀⠀⣼⠁⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣶⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠈⠲⢤⠞⠫⡤⠀⣠⣴⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⢠⡛⢉⣁⣻⣿⣿⣿⣿⣿⣷⣤⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⣠⠏⠠⢗⣢⣽⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀
⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⢠⣾⣿⣷⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀
⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣿⣿⣿⣿⠀⠀⠸⣿⣿⣿⡿⠿⣿⣿⣿⣿⣿⣿⣿⣇⣼⣿⣿⣿⣿⣿⣆
⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢁⡶⠒⠒⣿⣿⣿⡞⠂⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢃⡞⠀⠀⣼⣿⣿⣿⣿⢤⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣺⢄⣤⣾⣿⣿⣿⣿⠟⢁⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠠⡤⠬⣿⣿⣿⣿⣿⣮⠥⠤⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠠⠔⢲⠻⣿⣿⣿⣿⣿⣯⣭⡄⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣀⣠⠬⠛⠃⠀⠘⢿⡟⠛⣿⣿⣿⣿⣷⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏
⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⢿⣦⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇
⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣋⡿⡏⠀⠀⠀⠀⠀⠀⠀⠀⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠃
*/

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func NextInt() int {
	sc.Scan()
	return Atoi(sc.Text())
}

func NextString() string {
	sc.Scan()
	return sc.Text()
}

func Atoi(s string) int {
	i, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return i
}

func Output(v ...interface{}) {
	_, err := fmt.Fprintln(wr, v...)
	if err != nil {
		panic(err)
	}
}

func Flush() {
	err := wr.Flush()
	if err != nil {
		panic(err)
	}
}

func min(x, y int64) int64 {
	if x > y {
		return y
	}
	return x
}

func max(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func main() {
	defer Flush()

	n, c := NextInt(), NextInt()
	var all, sum, tmp int64 = 0, 0, 0
	var sumx, tmpx int64 = 0, 0

	for i := 0; i < n; i++ {
		x := NextInt()
		all += int64(x)
		tmp += int64(x)
		tmpx += int64(x)
		sum = max(sum, tmp)
		sumx = min(sumx, tmpx)
		tmp = max(0, tmp)
		tmpx = min(0, tmpx)
	}
	Output(max(sum*int64(c-1), sumx*int64(c-1)) + all)
	return
}

Java solution:
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.util.Arrays.setAll;
import static java.util.Arrays.sort;

import java.io.BufferedInputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.Supplier;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		long c = sc.nextLong();
		long[] arr = sc.nextLong(n);
		long sum = sc.getSum();
		if (c <= 0) {
			long ans = Long.MAX_VALUE;
			long s = 0;
			for (long a: arr) {
				s = min(s + a, a);
				ans = min(s, ans);
			}
			System.out.println(max(sum + (c - 1) * ans, sum));
		} else {
			long ans = Long.MIN_VALUE;
			long s = 0;
			for (long a: arr) {
				s = max(s + a, a);
				ans = max(s, ans);
			}
			System.out.println(max(sum + (c - 1) * ans, sum));
		}
	}

	/**
	 * 標準入力を高速に処理するためのクラスです。配列の入力時に総和、最大値、最小値を取得できます。
	 */
	@SuppressWarnings("unused")
	private static final class FastScanner {
		private static final BufferedInputStream reader = new BufferedInputStream(System.in);
		private static final byte[] buf = new byte[1 << 17];
		private static int pos = 0, cnt = 0;
		private long sum, low, high;

		/**
		 * バッファから1バイトを読み込みます。
		 *
		 * @return 読み込んだバイト（byte）
		 */
		private byte read() {
			if (pos == cnt) {
				try {
					cnt = reader.read(buf, pos = 0, 1 << 17);
				} catch (IOException ignored) {
				}
			}
			if (cnt < 0)
				return 0;
			return buf[pos++];
		}

		/**
		 * 次の一文字を読み込みます。
		 *
		 * @return 読み込んだ文字(char)
		 */
		public char nextChar() {
			byte b = read();
			while (b < '!' || '~' < b)
				b = read();
			return (char) b;
		}

		/**
		 * 次のトークンを文字列(String)として読み込みます。
		 *
		 * @return 読み込んだ文字列(String)
		 */
		public String next() {
			return nextSb().toString();
		}

		/**
		 * 次のトークンを文字列(StringBuilder)として読み込みます。
		 *
		 * @return 読み込んだ文字列(STringBuilder)
		 */
		public StringBuilder nextSb() {
			StringBuilder sb = new StringBuilder();
			int b = read();
			while (b < '!' || '~' < b)
				b = read();
			while ('!' <= b && b <= '~') {
				sb.appendCodePoint(b);
				b = read();
			}
			return sb;
		}

		/**
		 * 改行までの一行を読み込みます。
		 *
		 * @return 読み込んだ行(String)
		 */
		public String nextLine() {
			StringBuilder sb = new StringBuilder();
			int b = read();
			while (b != 0 && b != '\r' && b != '\n') {
				sb.appendCodePoint(b);
				b = read();
			}
			if (b == '\r')
				read();
			return sb.toString();
		}

		/**
		 * 次の整数を読み込みます。
		 *
		 * @return 読み込んだ整数(int)
		 */
		public int nextInt() {
			int b = nextChar();
			boolean neg = b == '-';
			if (neg)
				b = read();
			int n = 0;
			while ('0' <= b && b <= '9') {
				n = n * 10 + b - '0';
				b = read();
			}
			return neg ? -n : n;
		}

		/**
		 * 次の長整数を読み込みます。
		 *
		 * @return 読み込んだ長整数(long)
		 */
		public long nextLong() {
			int b = nextChar();
			boolean neg = b == '-';
			if (neg)
				b = read();
			long n = 0;
			while ('0' <= b && b <= '9') {
				n = n * 10 + b - '0';
				b = read();
			}
			return neg ? -n : n;
		}

		/**
		 * 基数を指定して整数を読み込みます。
		 *
		 * @param radix 基数
		 * @return 読み込んだ整数(int)
		 */
		public int nextIntRadix(int radix) {
			return Integer.parseInt(next(), radix);
		}

		/**
		 * 基数を指定して長整数を読み込みます。
		 *
		 * @param radix 基数
		 * @return 読み込んだ長整数(long)
		 */
		public long nextLongRadix(int radix) {
			return Long.parseLong(next(), radix);
		}

		/**
		 * 次のトークンをBigIntegerとして読み込みます。
		 *
		 * @return 読み込んだBigInteger
		 */
		public BigInteger nextBigInteger() {
			return new BigInteger(next());
		}

		/**
		 * 基数を指定してBigIntegerを読み込みます。
		 *
		 * @param radix 基数
		 * @return 読み込んだBigInteger
		 */
		public BigInteger nextBigInteger(int radix) {
			return new BigInteger(next(), radix);
		}

		/**
		 * 次のトークンを浮動小数点数として読み込みます。
		 *
		 * @return 読み込んだ浮動小数点数(double)
		 */
		public double nextDouble() {
			return Double.parseDouble(next());
		}

		/**
		 * 指定された長さの文字列配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ文字列配列(String[])
		 */
		public String[] nextStrings(int n) {
			String[] s = new String[n];
			setAll(s, x -> next());
			return s;
		}

		/**
		 * 指定された長さの文字列配列を読み込み、ソートされた文字列配列として返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた文字列配列(String[])
		 */
		public String[] nextSortedStrings(int n) {
			String[] s = nextStrings(n);
			sort(s);
			return s;
		}

		/**
		 * 指定された行数・列数の二次元文字列配列を読み込みます。
		 *
		 * @param n 行数
		 * @param m 列数
		 * @return 読み込んだ二次元文字列配列(String[][])
		 */
		public String[][] nextStringMat(int n, int m) {
			String[][] s = new String[n][m];
			setAll(s, x -> nextStrings(m));
			return s;
		}

		/**
		 * 次の文字列のi番目の文字を読み込みます。
		 *
		 * @param i 読み込む文字のindex
		 * @return 読み込んだ文字(char)
		 */
		public char nextCharAt(int i) {
			return next().charAt(i);
		}

		/**
		 * 文字列を文字配列として読み込みます。
		 *
		 * @return 読み込んだ文字配列(char[])
		 */
		public char[] nextChars() {
			return next().toCharArray();
		}

		/**
		 * 指定された長さの文字配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ文字配列(char[])
		 */
		public char[] nextChars(int n) {
			char[] c = new char[n];
			for (int i = 0; i < n; i++)
				c[i] = nextChar();
			return c;
		}

		/**
		 * 文字列を読み込み、ソートされた文字配列として返します。
		 *
		 * @return ソートされた文字配列(char[])
		 */
		public char[] nextSortedChars() {
			char[] c = nextChars();
			sort(c);
			return c;
		}

		/**
		 * 指定された長さの文字配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた文字配列(char[])
		 */
		public char[] nextSortedChars(int n) {
			char[] c = nextChars(n);
			sort(c);
			return c;
		}

		/**
		 * 複数の文字列を二次元の文字配列として読み込みます。
		 *
		 * @param n 行数（文字列の個数）
		 * @return 読み込んだ二次元文字配列(char[][])
		 */
		public char[][] nextCharMat(int n) {
			char[][] c = new char[n][];
			setAll(c, x -> nextChars());
			return c;
		}

		/**
		 * 指定された行数・列数の二次元文字配列を読み込みます。
		 *
		 * @param n 行数
		 * @param m 列数
		 * @return 読み込んだ二次元文字配列(char[][])
		 */
		public char[][] nextCharMat(int n, int m) {
			char[][] c = new char[n][m];
			setAll(c, x -> nextChars(m));
			return c;
		}

		/**
		 * 指定された長さの整数(int)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ整数配列(int[])
		 */
		public int[] nextInt(int n) {
			int[] a = new int[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextInt());
			return a;
		}

		/**
		 * 指定された長さの整数(Integer)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ整数配列(Integer[])
		 */
		public Integer[] nextInts(int n) {
			Integer[] a = new Integer[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextInt());
			return a;
		}

		/**
		 * 指定された長さの整数(int)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた整数配列(int[])
		 */
		public int[] nextSortedInt(int n) {
			int[] a = nextInt(n);
			sort(a);
			return a;
		}

		/**
		 * 指定された長さの整数(Integer)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた整数配列(Integer[])
		 */
		public Integer[] nextSortedInts(int n) {
			Integer[] a = nextInts(n);
			sort(a);
			return a;
		}

		/**
		 * 整数の累積和配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 累積和配列(int[])
		 */
		public int[] nextIntSum(int n) {
			int[] a = new int[n];
			resetStats();
			updateStats(a[0] = nextInt());
			for (int i = 1; i < n; i++) {
				updateStats(a[i] = nextInt());
				a[i] += a[i - 1];
			}
			return a;
		}

		/**
		 * 二次元整数配列を読み込みます。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 読み込んだ二次元整数配列(int[][])
		 */
		public int[][] nextIntMat(int h, int w) {
			int[][] a = new int[h][w];
			setAll(a, x -> nextInt(w));
			return a;
		}

		/**
		 * 二次元整数配列を読み込み、累積和配列として返します。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 二次元累積和配列(int[][])
		 */
		public int[][] nextIntMatSum(int h, int w) {
			int[][] a = new int[h + 1][w + 1];
			for (int i = 1; i <= h; i++)
				for (int j = 1; j <= w; j++)
					a[i][j] = nextInt() + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			return a;
		}

		/**
		 * 三次元整数配列を読み込みます。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 読み込んだ三次元整数配列(int[][][])
		 */
		public int[][][] nextInt3D(int x, int y, int z) {
			int[][][] a = new int[x][y][z];
			setAll(a, b -> nextIntMat(y, z));
			return a;
		}

		/**
		 * 三次元整数配列を読み込み、累積和配列として返します。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 三次元累積和配列(int[][][])
		 */
		public int[][][] nextIntSum3D(int x, int y, int z) {
			int[][][] e = new int[x + 1][y + 1][z + 1];
			for (int a = 1; a <= x; a++)
				for (int b = 1; b <= y; b++)
					for (int c = 1; c <= z; c++)
						e[a][b][c] = nextInt() + e[a - 1][b][c] + e[a][b - 1][c] + e[a][b][c - 1] - e[a - 1][b - 1][c]
								- e[a - 1][b][c - 1] - e[a][b - 1][c - 1] + e[a - 1][b - 1][c - 1];
			return e;
		}

		/**
		 * 指定された長さの長整数(long)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ長整数配列(long[])
		 */
		public long[] nextLong(int n) {
			long[] a = new long[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextLong());
			return a;
		}

		/**
		 * 指定された長さの長整数(Long)配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 読み込んだ長整数配列(Long[])
		 */
		public Long[] nextLongs(int n) {
			Long[] a = new Long[n];
			resetStats();
			for (int i = 0; i < n; i++)
				updateStats(a[i] = nextLong());
			return a;
		}

		/**
		 * 指定された長さの長整数(long)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた長整数配列(long[])
		 */
		public long[] nextSortedLong(int n) {
			long[] a = nextLong(n);
			sort(a);
			return a;
		}

		/**
		 * 指定された長さの長整数(Long)配列を読み込み、ソートして返します。
		 *
		 * @param n 配列の長さ
		 * @return ソートされた長整数配列(Long[])
		 */
		public Long[] nextSortedLongs(int n) {
			Long[] a = nextLongs(n);
			sort(a);
			return a;
		}

		/**
		 * 長整数の累積和配列を読み込みます。
		 *
		 * @param n 配列の長さ
		 * @return 累積和配列(long[])
		 */
		public long[] nextLongSum(int n) {
			long[] a = new long[n];
			low = high = sum = a[0] = nextLong();
			for (int i = 1; i < n; i++) {
				updateStats(a[i] = nextLong());
				a[i] += a[i - 1];
			}
			return a;
		}

		/**
		 * 二次元長整数配列を読み込みます。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 読み込んだ二次元長整数配列(long[])
		 */
		public long[][] nextLongMat(int h, int w) {
			long[][] a = new long[h][w];
			setAll(a, x -> nextLong(w));
			return a;
		}

		/**
		 * 二次元長整数配列を読み込み、累積和配列として返します。
		 *
		 * @param h 行数
		 * @param w 列数
		 * @return 二次元累積和配列(long[][])
		 */
		public long[][] nextLongMatSum(int h, int w) {
			long[][] a = new long[h + 1][w + 1];
			for (int i = 1; i <= h; i++)
				for (int j = 1; j <= w; j++)
					a[i][j] = nextLong() + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
			return a;
		}

		/**
		 * 三次元長整数配列を読み込みます。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 読み込んだ三次元長整数配列(long[][])
		 */
		public long[][][] nextLong3D(int x, int y, int z) {
			long[][][] a = new long[x][y][z];
			setAll(a, b -> nextLongMat(y, z));
			return a;
		}

		/**
		 * 三次元長整数配列を読み込み、累積和配列として返します。
		 *
		 * @param x サイズX
		 * @param y サイズY
		 * @param z サイズZ
		 * @return 三次元累積和配列(long[][][])
		 */
		public long[][][] nextLongSum3D(int x, int y, int z) {
			long[][][] e = new long[x + 1][y + 1][z + 1];
			for (int a = 1; a <= x; a++)
				for (int b = 1; b <= y; b++)
					for (int c = 1; c <= z; c++)
						e[a][b][c] = nextLong() + e[a - 1][b][c] + e[a][b - 1][c] + e[a][b][c - 1] - e[a - 1][b - 1][c]
								- e[a - 1][b][c - 1] - e[a][b - 1][c - 1] + e[a - 1][b - 1][c - 1];
			return e;
		}

		/**
		 * 整数を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<Integer>> T nextIntCollection(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				int a = nextInt();
				c.add(a);
				updateStats(a);
			}
			return c;
		}

		/**
		 * 指定された長さの整数のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<Integer> nextIntAL(int n) {
			return nextIntCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの整数のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<Integer> nextIntLL(int n) {
			return nextIntCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの整数を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<Integer> nextIntHS(int n) {
			return nextIntCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの整数を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<Integer> nextIntLHS(int n) {
			return nextIntCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの整数を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<Integer> nextIntTS(int n) {
			return nextIntCollection(n, TreeSet::new);
		}

		/**
		 * 長整数を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<Long>> T nextLongCollection(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				long a = nextLong();
				c.add(a);
				updateStats(a);
			}
			return c;
		}

		/**
		 * 指定された長さの整数のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<Long> nextLongAL(int n) {
			return nextLongCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの整数のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<Long> nextLongLL(int n) {
			return nextLongCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの長整数を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<Long> nextLongHS(int n) {
			return nextLongCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの長整数を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<Long> nextLongLHS(int n) {
			return nextLongCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの長整数を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<Long> nextLongTS(int n) {
			return nextLongCollection(n, TreeSet::new);
		}

		/**
		 * 文字列を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<String>> T nextStringCollection(int n, Supplier<T> s) {
			T c = s.get();
			while (n-- > 0) {
				c.add(next());
			}
			return c;
		}

		/**
		 * 指定された長さの文字列のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<String> nextStringAL(int n) {
			return nextStringCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの文字列のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<String> nextStringLL(int n) {
			return nextStringCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの文字列を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<String> nextStringHS(int n) {
			return nextStringCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの文字列を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<String> nextStringLHS(int n) {
			return nextStringCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの文字列を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<String> nextStringTS(int n) {
			return nextStringCollection(n, TreeSet::new);
		}

		/**
		 * 文字を含むコレクションを読み込みます。
		 *
		 * @param <T> コレクションの型
		 * @param n   要素数
		 * @param s   コレクションのサプライヤー
		 * @return 読み込んだコレクション(Collection)
		 */
		private <T extends Collection<Character>> T nextCharacterCollection(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				char t = nextChar();
				c.add(t);
				updateStats(t);
			}
			return c;
		}

		/**
		 * 指定された長さの文字のArrayListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだArrayList
		 */
		public ArrayList<Character> nextCharacterAL(int n) {
			return nextCharacterCollection(n, ArrayList::new);
		}

		/**
		 * 指定された長さの文字のLinkedListを読み込みます。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedList
		 */
		public LinkedList<Character> nextCharacterLL(int n) {
			return nextCharacterCollection(n, LinkedList::new);
		}

		/**
		 * 指定された長さの文字を読み込んだHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashSet
		 */
		public HashSet<Character> nextCharacterHS(int n) {
			return nextCharacterCollection(n, HashSet::new);
		}

		/**
		 * 指定された長さの文字を読み込んだLinkedHashSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashSet
		 */
		public LinkedHashSet<Character> nextCharacterLHS(int n) {
			return nextCharacterCollection(n, LinkedHashSet::new);
		}

		/**
		 * 指定された長さの文字を読み込んだTreeSetを返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだTreeSet
		 */
		public TreeSet<Character> nextCharacterTS(int n) {
			return nextCharacterCollection(n, TreeSet::new);
		}

		/**
		 * 整数をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<Integer, Integer>> T nextIntMultiset(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				int a = nextInt();
				c.put(a, c.getOrDefault(a, 0) + 1);
				updateStats(a);
			}
			return c;
		}

		/**
		 * Key(Integer)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<Integer, Integer> nextIntMultisetHM(int n) {
			return nextIntMultiset(n, HashMap::new);
		}

		/**
		 * Key(Integer)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<Integer, Integer> nextIntMultisetLHM(int n) {
			return nextIntMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(Integer)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<Integer, Integer> nextIntMultisetTM(int n) {
			return nextIntMultiset(n, TreeMap::new);
		}

		/**
		 * 長整数をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<Long, Integer>> T nextLongMultiset(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				long a = nextLong();
				c.put(a, c.getOrDefault(a, 0) + 1);
				updateStats(a);
			}
			return c;
		}

		/**
		 * Key(Long)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<Long, Integer> nextLongMultisetHM(int n) {
			return nextLongMultiset(n, HashMap::new);
		}

		/**
		 * Key(Long)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<Long, Integer> nextLongMultisetLHM(int n) {
			return nextLongMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(Long)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<Long, Integer> nextLongMultisetTM(int n) {
			return nextLongMultiset(n, TreeMap::new);
		}

		/**
		 * 文字列をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<String, Integer>> T nextStringMultiset(int n, Supplier<T> s) {
			T c = s.get();
			while (n-- > 0) {
				String a = next();
				c.put(a, c.getOrDefault(a, 0) + 1);
			}
			return c;
		}

		/**
		 * Key(String)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<String, Integer> nextStringMultisetHM(int n) {
			return nextStringMultiset(n, HashMap::new);
		}

		/**
		 * Key(String)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<String, Integer> nextStringMultisetLHM(int n) {
			return nextStringMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(String)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<String, Integer> nextStringMultisetTM(int n) {
			return nextStringMultiset(n, TreeMap::new);
		}

		/**
		 * 文字をKey、出現回数をValueとするMapを読み込みます。
		 *
		 * @param <T> Mapの型
		 * @param n   要素数
		 * @param s   Mapのサプライヤー
		 * @return 読み込んだMap
		 */
		private <T extends Map<Character, Integer>> T nextCharMultiset(int n, Supplier<T> s) {
			T c = s.get();
			resetStats();
			while (n-- > 0) {
				char a = nextChar();
				c.put(a, c.getOrDefault(a, 0) + 1);
				updateStats(a);
			}
			return c;
		}

		/**
		 * Key(Character)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだHashMap
		 */
		public HashMap<Character, Integer> nextCharMultisetHM(int n) {
			return nextCharMultiset(n, HashMap::new);
		}

		/**
		 * Key(Character)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 要素数
		 * @return 読み込んだLinkedHashMap
		 */
		public LinkedHashMap<Character, Integer> nextCharacterMultisetLHM(int n) {
			return nextCharMultiset(n, LinkedHashMap::new);
		}

		/**
		 * Key(Character)に対しValueをその出現回数とする写像を返します。
		 *
		 * @param n 読み込む配列の長さ
		 * @return 読み込んだTreeMap
		 */
		public TreeMap<Character, Integer> nextCharMultisetTM(int n) {
			return nextCharMultiset(n, TreeMap::new);
		}

		/**
		 * 読み込んだ配列の最小値を返します。
		 *
		 * @return 最小値
		 */
		public long getLowestNum() {
			return low;
		}

		/**
		 * 読み込んだ配列の最大値を返します。
		 *
		 * @return 最大値
		 */
		public long getHighestNum() {
			return high;
		}

		/**
		 * 読み込んだ配列の総和を返します。
		 *
		 * @return 総和
		 */
		public long getSum() {
			return sum;
		}

		/**
		 * 統計情報をリセットします（最小値、最大値、総和）。
		 */
		private void resetStats() {
			low = Long.MAX_VALUE;
			high = Long.MIN_VALUE;
			sum = 0;
		}

		/**
		 * 読み込んだ値で統計情報（最小値、最大値、総和）を更新します。
		 *
		 * @param a 更新する値
		 */
		private void updateStats(long a) {
			sum += a;
			low = min(low, a);
			high = max(high, a);
		}
	}
}

JavaScript solution:
/// source code (in typescript)

// // @kariay1975/atcoder-tslib is a private package: 
// import {
//   Input,
//   InputStdin,
//   LazySegmentTree,
//   Output,
//   accumulationSum,
//   bigmax,
//   int,
//   intmax,
//   intmin,
//   isControlTag,
//   withLog,
// } from '@kariya1975/atcoder-tslib';
// // use babel-plugin-macros for speed.
// import {
//   arrayWith,
//   enumerate,
//   range,
// } from '@kariya1975/atcoder-tslib/macro';
// 
// 
// // const solve = (N: int, C: int, A: int[]): bigint => {
// //   const acc = accumulationSum(A).map(n => BigInt(n));
// //   const c = BigInt(C - 1);
// //   const acc2 = acc.map(n => c * n);
// //   const f = withLog('f')((l: int, r: int): bigint => {
// //     return acc[N] + acc2[r + 1] - acc2[l];
// //   });
// //   const accMax = arrayWith(N + 1, () => 0n);
// //   accMax[N] = acc[N];
// //   for (const i of range(N - 1, 0, -1)) {
// //     accMax[i] = bigmax(acc[i], accMax[i + 1]);
// //   }
// // console.error(acc, accMax)
// //   let result = acc[N];
// //   for (const l of range(N)) {
// //     for (const r of range(l, N)) {
// //       const t = f(l, r);
// //       result = bigmax(result, t);
// //     }
// //   }
// //   return result;
// // };
// 
// const solve1 = (N: int, C: int, A: int[]): bigint => {
//   const acc = accumulationSum(A).map(n => BigInt(n));
//   const c = BigInt(C - 1);
//   const acc2 = acc.map(n => c * n);
//   const f = withLog('f')((l: int, r: int): bigint => {
//     return acc[N] + acc2[r + 1] - acc2[l];
//   });
//   const t = new LazySegmentTree<bigint, bigint>(
//     N + 1,
//     (x, y) => bigmax(x, y),
//     -(10n**20n),
//     (f, x) => bigmax(f, x),
//     (f, g) => bigmax(f, g),
//     -(10n**20n),
//   );
//   const acc2i = acc2.map((v, i) => ({v, i}));
//   acc2i.sort((x, y) => y.v > x.v ? -1 : y.v < x.v ? 1 : 0);
//   for (const {i, v} of acc2i) {
//     t.apply2(0, i, v);
//   }
// // console.error(acc, acc2i)
//   let result = acc[N];
//   for (const l of range(N)) {
//     const v = t.get(l);
//     const t3 = acc[N] + v - acc2[l];
//     result = bigmax(result, t3);
//   }
//   return result;
// };
// 
// export const maxIntervalSum = (xs: int[]): int => {
//   let s = 0;
//   let mini = 0;
//   let result = 0;
//   for (const x of xs) {
//     s += x;
//     mini = intmin(mini, s);
//     result = intmax(result, s - mini);
//   }
//   return result;
// };
// export const minIntervalSum = (xs: int[]): int => {
//   let s = 0;
//   let maxi = 0;
//   let result = 0;
//   for (const x of xs) {
//     s += x;
//     maxi = intmax(maxi, s);
//     result = intmin(result, s - maxi);
//   }
//   return result;
// };
// 
// const solve = (N: int, C: int, A: int[]): bigint => {
//   let s = 0;
//   for (const a of A) {
//     s += a;
//   }
// 
//   if (C >= 1) {
//     const t = maxIntervalSum(A);
//     return BigInt(s) + BigInt(C - 1) * BigInt(t);
//   } else {
//     const t = minIntervalSum(A);
//     return BigInt(s) + BigInt(C - 1) * BigInt(t);
//   }
// };
// 
// const main = (input: Input, output: Output): void => {
//   const [N, C] = input.getInts(2);
//   const A = input.getInts(N);
//   const result = solve(N, C, A);
//   output.push(result);
// };
// 
// const input = new InputStdin();
// input.setup().then(_ => {
//   const output = new Output();
//   try {
//     main(input, output);
//     output.print();
//   } catch (e) {
//     if (isControlTag(e, 'earlyExit')) {
//       output.print();
//     } else {
//       throw e;
//     }
//   }
// }).catch(e => {
//   console.error(e);
// });

// /// The code above transpiles as follows:
var it=Object.create;var k=Object.defineProperty;var nt=Object.getOwnPropertyDescriptor;var st=Object.getOwnPropertyNames;var ot=Object.getPrototypeOf,ht=Object.prototype.hasOwnProperty;var T=(i,t)=>()=>(t||i((t={exports:{}}).exports,t),t.exports),lt=(i,t)=>{for(var e in t)k(i,e,{get:t[e],enumerable:!0})},L=(i,t,e,r)=>{if(t&&typeof t=="object"||typeof t=="function")for(let n of st(t))!ht.call(i,n)&&n!==e&&k(i,n,{get:()=>t[n],enumerable:!(r=nt(t,n))||r.enumerable});return i};var F=(i,t,e)=>(e=i!=null?it(ot(i)):{},L(t||!i||!i.__esModule?k(e,"default",{value:i,enumerable:!0}):e,i)),ut=i=>L(k({},"__esModule",{value:!0}),i);var C=T((Ht,$)=>{"use strict";var at=function(i,t){return i<t};function d(i){if(!(this instanceof d))return new d(i);this.array=[],this.size=0,this.compare=i||at}d.prototype.clone=function(){var i=new d(this.compare);return i.size=this.size,i.array=this.array.slice(0,this.size),i};d.prototype.add=function(i){var t=this.size;this.array[this.size]=i,this.size+=1;for(var e,r;t>0&&(e=t-1>>1,r=this.array[e],!!this.compare(i,r));)this.array[t]=r,t=e;this.array[t]=i};d.prototype.heapify=function(i){this.array=i,this.size=i.length;var t;for(t=this.size>>1;t>=0;t--)this._percolateDown(t)};d.prototype._percolateUp=function(i,t){for(var e=this.array[i],r,n;i>0&&(r=i-1>>1,n=this.array[r],!(!t&&!this.compare(e,n)));)this.array[i]=n,i=r;this.array[i]=e};d.prototype._percolateDown=function(i){for(var t=this.size,e=this.size>>>1,r=this.array[i],n,s,o;i<e&&(n=(i<<1)+1,s=n+1,o=this.array[n],s<t&&this.compare(this.array[s],o)&&(n=s,o=this.array[s]),!!this.compare(o,r));)this.array[i]=o,i=n;this.array[i]=r};d.prototype._removeAt=function(i){if(!(i>this.size-1||i<0))return this._percolateUp(i,!0),this.poll()};d.prototype.remove=function(i){for(var t=0;t<this.size;t++)if(!this.compare(this.array[t],i)&&!this.compare(i,this.array[t]))return this._removeAt(t),!0;return!1};d.prototype.removeOne=function(i){if(typeof i=="function"){for(var t=0;t<this.size;t++)if(i(this.array[t]))return this._removeAt(t)}};d.prototype.removeMany=function(i,t){if(typeof i!="function"||this.size<1)return[];t=t?Math.min(t,this.size):this.size;for(var e=0,r=new Array(t),n=0,s=new Array(this.size);e<t&&!this.isEmpty();){var o=this.poll();i(o)?r[e++]=o:s[n++]=o}r.length=e;for(var h=0;h<n;)this.add(s[h++]);return r};d.prototype.peek=function(){if(this.size!=0)return this.array[0]};d.prototype.poll=function(){if(this.size!=0){var i=this.array[0];return this.size>1?(this.array[0]=this.array[--this.size],this._percolateDown(0)):this.size-=1,i}};d.prototype.replaceTop=function(i){if(this.size!=0){var t=this.array[0];return this.array[0]=i,this._percolateDown(0),t}};d.prototype.trim=function(){this.array=this.array.slice(0,this.size)};d.prototype.isEmpty=function(){return this.size===0};d.prototype.forEach=function(i){if(!(this.isEmpty()||typeof i!="function"))for(var t=0,e=this.clone();!e.isEmpty();)i(e.poll(),t++)};d.prototype.kSmallest=function(i){if(this.size==0)return[];i=Math.min(this.size,i);var t=new d(this.compare);let e=Math.min((i>0?Math.pow(2,i-1):0)+1,this.size);t.size=e,t.array=this.array.slice(0,e);for(var r=new Array(i),n=0;n<i;n++)r[n]=t.poll();return r};$.exports=d});var j=T((ne,K)=>{"use strict";function c(i){if(this._capacity=W(i),this._length=0,this._front=0,P(i)){for(var t=i.length,e=0;e<t;++e)this[e]=i[e];this._length=t}}c.prototype.toArray=function(){for(var t=this._length,e=new Array(t),r=this._front,n=this._capacity,s=0;s<t;++s)e[s]=this[r+s&n-1];return e};c.prototype.push=function(t){var e=arguments.length,r=this._length;if(e>1){var n=this._capacity;if(r+e>n){for(var o=0;o<e;++o){this._checkCapacity(r+1);var s=this._front+r&this._capacity-1;this[s]=arguments[o],r++,this._length=r}return r}else{for(var s=this._front,o=0;o<e;++o)this[s+r&n-1]=arguments[o],s++;return this._length=r+e,r+e}}if(e===0)return r;this._checkCapacity(r+1);var o=this._front+r&this._capacity-1;return this[o]=t,this._length=r+1,r+1};c.prototype.pop=function(){var t=this._length;if(t!==0){var e=this._front+t-1&this._capacity-1,r=this[e];return this[e]=void 0,this._length=t-1,r}};c.prototype.shift=function(){var t=this._length;if(t!==0){var e=this._front,r=this[e];return this[e]=void 0,this._front=e+1&this._capacity-1,this._length=t-1,r}};c.prototype.unshift=function(t){var e=this._length,r=arguments.length;if(r>1){var o=this._capacity;if(e+r>o){for(var h=r-1;h>=0;h--){this._checkCapacity(e+1);var o=this._capacity,n=(this._front-1&o-1^o)-o;this[n]=arguments[h],e++,this._length=e,this._front=n}return e}else{for(var s=this._front,h=r-1;h>=0;h--){var n=(s-1&o-1^o)-o;this[n]=arguments[h],s=n}return this._front=s,this._length=e+r,e+r}}if(r===0)return e;this._checkCapacity(e+1);var o=this._capacity,h=(this._front-1&o-1^o)-o;return this[h]=t,this._length=e+1,this._front=h,e+1};c.prototype.peekBack=function(){var t=this._length;if(t!==0){var e=this._front+t-1&this._capacity-1;return this[e]}};c.prototype.peekFront=function(){if(this._length!==0)return this[this._front]};c.prototype.get=function(t){var e=t;if(e===(e|0)){var r=this._length;if(e<0&&(e=e+r),!(e<0||e>=r))return this[this._front+e&this._capacity-1]}};c.prototype.isEmpty=function(){return this._length===0};c.prototype.clear=function(){for(var t=this._length,e=this._front,r=this._capacity,n=0;n<t;++n)this[e+n&r-1]=void 0;this._length=0,this._front=0};c.prototype.toString=function(){return this.toArray().toString()};c.prototype.valueOf=c.prototype.toString;c.prototype.removeFront=c.prototype.shift;c.prototype.removeBack=c.prototype.pop;c.prototype.insertFront=c.prototype.unshift;c.prototype.insertBack=c.prototype.push;c.prototype.enqueue=c.prototype.push;c.prototype.dequeue=c.prototype.shift;c.prototype.toJSON=c.prototype.toArray;Object.defineProperty(c.prototype,"length",{get:function(){return this._length},set:function(){throw new RangeError("")}});c.prototype._checkCapacity=function(t){this._capacity<t&&this._resizeTo(W(this._capacity*1.5+16))};c.prototype._resizeTo=function(t){var e=this._capacity;this._capacity=t;var r=this._front,n=this._length;if(r+n>e){var s=r+n&e-1;mt(this,0,this,e,s)}};var P=Array.isArray;function mt(i,t,e,r,n){for(var s=0;s<n;++s)e[s+r]=i[s+t],i[s+t]=void 0}function gt(i){return i=i>>>0,i=i-1,i=i|i>>1,i=i|i>>2,i=i|i>>4,i=i|i>>8,i=i|i>>16,i+1}function W(i){if(typeof i!="number")if(P(i))i=i.length;else return 16;return gt(Math.min(Math.max(16,i),1073741824))}K.exports=c});var U=T((Be,Q)=>{"use strict";Q.exports=qt;var f=0,a=1;function _(i,t,e,r,n,s){this._color=i,this.key=t,this.value=e,this.left=r,this.right=n,this._count=s}function z(i){return new _(i._color,i.key,i.value,i.left,i.right,i._count)}function I(i,t){return new _(i,t.key,t.value,t.left,t.right,t._count)}function p(i){i._count=1+(i.left?i.left._count:0)+(i.right?i.right._count:0)}function S(i,t){this._compare=i,this.root=t}var v=S.prototype;Object.defineProperty(v,"keys",{get:function(){var i=[];return this.forEach(function(t,e){i.push(t)}),i}});Object.defineProperty(v,"values",{get:function(){var i=[];return this.forEach(function(t,e){i.push(e)}),i}});Object.defineProperty(v,"length",{get:function(){return this.root?this.root._count:0}});v.insert=function(i,t){for(var e=this._compare,r=this.root,n=[],s=[];r;){var o=e(i,r.key);n.push(r),s.push(o),o<=0?r=r.left:r=r.right}n.push(new _(f,i,t,null,null,1));for(var h=n.length-2;h>=0;--h){var r=n[h];s[h]<=0?n[h]=new _(r._color,r.key,r.value,n[h+1],r.right,r._count+1):n[h]=new _(r._color,r.key,r.value,r.left,n[h+1],r._count+1)}for(var h=n.length-1;h>1;--h){var l=n[h-1],r=n[h];if(l._color===a||r._color===a)break;var u=n[h-2];if(u.left===l)if(l.left===r){var g=u.right;if(g&&g._color===f)l._color=a,u.right=I(a,g),u._color=f,h-=1;else{if(u._color=f,u.left=l.right,l._color=a,l.right=u,n[h-2]=l,n[h-1]=r,p(u),p(l),h>=3){var y=n[h-3];y.left===u?y.left=l:y.right=l}break}}else{var g=u.right;if(g&&g._color===f)l._color=a,u.right=I(a,g),u._color=f,h-=1;else{if(l.right=r.left,u._color=f,u.left=r.right,r._color=a,r.left=l,r.right=u,n[h-2]=r,n[h-1]=l,p(u),p(l),p(r),h>=3){var y=n[h-3];y.left===u?y.left=r:y.right=r}break}}else if(l.right===r){var g=u.left;if(g&&g._color===f)l._color=a,u.left=I(a,g),u._color=f,h-=1;else{if(u._color=f,u.right=l.left,l._color=a,l.left=u,n[h-2]=l,n[h-1]=r,p(u),p(l),h>=3){var y=n[h-3];y.right===u?y.right=l:y.left=l}break}}else{var g=u.left;if(g&&g._color===f)l._color=a,u.left=I(a,g),u._color=f,h-=1;else{if(l.left=r.right,u._color=f,u.right=r.left,r._color=a,r.right=l,r.left=u,n[h-2]=r,n[h-1]=l,p(u),p(l),p(r),h>=3){var y=n[h-3];y.right===u?y.right=r:y.left=r}break}}}return n[0]._color=a,new S(e,n[0])};var It=B(function i(t,e){if(e.left){var r=i(t,e.left);if(r)return r}var r=t(e.key,e.value);if(r)return r;if(e.right)return()=>i(t,e.right)}),St=B(function i(t,e,r,n){var s=e(t,n.key);if(s<=0){if(n.left){var o=i(t,e,r,n.left);if(o)return o}var o=r(n.key,n.value);if(o)return o}if(n.right)return()=>i(t,e,r,n.right)}),bt=B(function i(t,e,r,n,s){var o=r(t,s.key),h=r(e,s.key),l;if(o<=0&&(s.left&&(l=i(t,e,r,n,s.left),l)||h>0&&(l=n(s.key,s.value),l)))return l;if(h>0&&s.right)return()=>i(t,e,r,n,s.right)});v.forEach=function(t,e,r){if(this.root)switch(arguments.length){case 1:return It(t,this.root);case 2:return St(e,this._compare,t,this.root);case 3:return this._compare(e,r)>=0?void 0:bt(e,r,this._compare,t,this.root)}};Object.defineProperty(v,"begin",{get:function(){for(var i=[],t=this.root;t;)i.push(t),t=t.left;return new w(this,i)}});Object.defineProperty(v,"end",{get:function(){for(var i=[],t=this.root;t;)i.push(t),t=t.right;return new w(this,i)}});v.at=function(i){if(i<0)return new w(this,[]);for(var t=this.root,e=[];;){if(e.push(t),t.left){if(i<t.left._count){t=t.left;continue}i-=t.left._count}if(!i)return new w(this,e);if(i-=1,t.right){if(i>=t.right._count)break;t=t.right}else break}return new w(this,[])};v.ge=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s<=0&&(n=r.length),s<=0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.gt=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s<0&&(n=r.length),s<0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.lt=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s>0&&(n=r.length),s<=0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.le=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s>=0&&(n=r.length),s<0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.find=function(i){for(var t=this._compare,e=this.root,r=[];e;){var n=t(i,e.key);if(r.push(e),n===0)return new w(this,r);n<=0?e=e.left:e=e.right}return new w(this,[])};v.remove=function(i){var t=this.find(i);return t?t.remove():this};v.get=function(i){for(var t=this._compare,e=this.root;e;){var r=t(i,e.key);if(r===0)return e.value;r<=0?e=e.left:e=e.right}};function w(i,t){this.tree=i,this._stack=t}var x=w.prototype;Object.defineProperty(x,"valid",{get:function(){return this._stack.length>0}});Object.defineProperty(x,"node",{get:function(){return this._stack.length>0?this._stack[this._stack.length-1]:null},enumerable:!0});x.clone=function(){return new w(this.tree,this._stack.slice())};function G(i,t){i.key=t.key,i.value=t.value,i.left=t.left,i.right=t.right,i._color=t._color,i._count=t._count}function At(i){for(var t,e,r,n,s=i.length-1;s>=0;--s){if(t=i[s],s===0){t._color=a;return}if(e=i[s-1],e.left===t){if(r=e.right,r.right&&r.right._color===f){if(r=e.right=z(r),n=r.right=z(r.right),e.right=r.left,r.left=e,r.right=n,r._color=e._color,t._color=a,e._color=a,n._color=a,p(e),p(r),s>1){var o=i[s-2];o.left===e?o.left=r:o.right=r}i[s-1]=r;return}else if(r.left&&r.left._color===f){if(r=e.right=z(r),n=r.left=z(r.left),e.right=n.left,r.left=n.right,n.left=e,n.right=r,n._color=e._color,e._color=a,r._color=a,t._color=a,p(e),p(r),p(n),s>1){var o=i[s-2];o.left===e?o.left=n:o.right=n}i[s-1]=n;return}if(r._color===a)if(e._color===f){e._color=a,e.right=I(f,r);return}else{e.right=I(f,r);continue}else{if(r=z(r),e.right=r.left,r.left=e,r._color=e._color,e._color=f,p(e),p(r),s>1){var o=i[s-2];o.left===e?o.left=r:o.right=r}i[s-1]=r,i[s]=e,s+1<i.length?i[s+1]=t:i.push(t),s=s+2}}else{if(r=e.left,r.left&&r.left._color===f){if(r=e.left=z(r),n=r.left=z(r.left),e.left=r.right,r.right=e,r.left=n,r._color=e._color,t._color=a,e._color=a,n._color=a,p(e),p(r),s>1){var o=i[s-2];o.right===e?o.right=r:o.left=r}i[s-1]=r;return}else if(r.right&&r.right._color===f){if(r=e.left=z(r),n=r.right=z(r.right),e.left=n.right,r.right=n.left,n.right=e,n.left=r,n._color=e._color,e._color=a,r._color=a,t._color=a,p(e),p(r),p(n),s>1){var o=i[s-2];o.right===e?o.right=n:o.left=n}i[s-1]=n;return}if(r._color===a)if(e._color===f){e._color=a,e.left=I(f,r);return}else{e.left=I(f,r);continue}else{if(r=z(r),e.left=r.right,r.right=e,r._color=e._color,e._color=f,p(e),p(r),s>1){var o=i[s-2];o.right===e?o.right=r:o.left=r}i[s-1]=r,i[s]=e,s+1<i.length?i[s+1]=t:i.push(t),s=s+2}}}}x.remove=function(){var i=this._stack;if(i.length===0)return this.tree;var t=new Array(i.length),e=i[i.length-1];t[t.length-1]=new _(e._color,e.key,e.value,e.left,e.right,e._count);for(var r=i.length-2;r>=0;--r){var e=i[r];e.left===i[r+1]?t[r]=new _(e._color,e.key,e.value,t[r+1],e.right,e._count):t[r]=new _(e._color,e.key,e.value,e.left,t[r+1],e._count)}if(e=t[t.length-1],e.left&&e.right){var n=t.length;for(e=e.left;e.right;)t.push(e),e=e.right;var s=t[n-1];t.push(new _(e._color,s.key,s.value,e.left,e.right,e._count)),t[n-1].key=e.key,t[n-1].value=e.value;for(var r=t.length-2;r>=n;--r)e=t[r],t[r]=new _(e._color,e.key,e.value,e.left,t[r+1],e._count);t[n-1].left=t[n]}if(e=t[t.length-1],e._color===f){var o=t[t.length-2];o.left===e?o.left=null:o.right===e&&(o.right=null),t.pop();for(var r=0;r<t.length;++r)t[r]._count--;return new S(this.tree._compare,t[0])}else if(e.left||e.right){e.left?G(e,e.left):e.right&&G(e,e.right),e._color=a;for(var r=0;r<t.length-1;++r)t[r]._count--;return new S(this.tree._compare,t[0])}else{if(t.length===1)return new S(this.tree._compare,null);for(var r=0;r<t.length;++r)t[r]._count--;var h=t[t.length-2];At(t),h.left===e?h.left=null:h.right=null}return new S(this.tree._compare,t[0])};Object.defineProperty(x,"key",{get:function(){if(this._stack.length>0)return this._stack[this._stack.length-1].key},enumerable:!0});Object.defineProperty(x,"value",{get:function(){if(this._stack.length>0)return this._stack[this._stack.length-1].value},enumerable:!0});Object.defineProperty(x,"index",{get:function(){var i=0,t=this._stack;if(t.length===0){var e=this.tree.root;return e?e._count:0}else t[t.length-1].left&&(i=t[t.length-1].left._count);for(var r=t.length-2;r>=0;--r)t[r+1]===t[r].right&&(++i,t[r].left&&(i+=t[r].left._count));return i},enumerable:!0});x.next=function(){var i=this._stack;if(i.length!==0){var t=i[i.length-1];if(t.right)for(t=t.right;t;)i.push(t),t=t.left;else for(i.pop();i.length>0&&i[i.length-1].right===t;)t=i[i.length-1],i.pop()}};Object.defineProperty(x,"hasNext",{get:function(){var i=this._stack;if(i.length===0)return!1;if(i[i.length-1].right)return!0;for(var t=i.length-1;t>0;--t)if(i[t-1].left===i[t])return!0;return!1}});x.update=function(i){var t=this._stack;if(t.length===0)throw new Error("Can't update empty node!");var e=new Array(t.length),r=t[t.length-1];e[e.length-1]=new _(r._color,r.key,i,r.left,r.right,r._count);for(var n=t.length-2;n>=0;--n)r=t[n],r.left===t[n+1]?e[n]=new _(r._color,r.key,r.value,e[n+1],r.right,r._count):e[n]=new _(r._color,r.key,r.value,r.left,e[n+1],r._count);return new S(this.tree._compare,e[0])};x.prev=function(){var i=this._stack;if(i.length!==0){var t=i[i.length-1];if(t.left)for(t=t.left;t;)i.push(t),t=t.right;else for(i.pop();i.length>0&&i[i.length-1].left===t;)t=i[i.length-1],i.pop()}};Object.defineProperty(x,"hasPrev",{get:function(){var i=this._stack;if(i.length===0)return!1;if(i[i.length-1].left)return!0;for(var t=i.length-1;t>0;--t)if(i[t-1].right===i[t])return!0;return!1}});function Nt(i,t){return i<t?-1:i>t?1:0}function qt(i){return new S(i||Nt,null)}function B(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}});var Pt={};lt(Pt,{maxIntervalSum:()=>et,minIntervalSum:()=>rt});module.exports=ut(Pt);var A=require("fs"),M=class{constructor(t){this.data=t!=null?t:"",this.index=0}isSpace(t){return t===" "||t===`
`}getString(){for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;let t=this.index;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)this.index++;let e=this.index;return this.data.slice(t,e)}getCharList(){let t=[];for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)t.push(this.data[this.index]),this.index++;return t}getBigInt(){return BigInt(this.getString())}getInt(){return Number(this.getString())}getNumber(){return Number(this.getString())}getNumbers(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getNumber());return e}getBigInts(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getBigInt());return e}getInts(t){let e=Array(t);for(let r=0,n=t;r<n;++r)e[r]=this.getInt();return e}getStrings(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getString());return e}getMatrix(){let[t,e]=this.getInts(2),r=[];for(let n=0,s=t;n<s;++n)r.push(this.getInts(e));return[t,e,r]}getMatrixWithExtraData(t){let[e,r]=this.getInts(2),n=this.getInts(t),s=[];for(let o=0,h=e;o<h;++o)s.push(this.getInts(r));return[e,r,n,s]}getSquareMatrix(){let t=this.getInt(),e=[];for(let r=0,n=t;r<n;++r)e.push(this.getInts(t));return[t,e]}forEach(t){let e=this.getInt();for(let r=0,n=e;r<n;++r)t(r)}case(t){let e=this.getInt();if(!t.has(e))throw new Error(`unknown kind ${e}`);t.get(e)(e)}getSeries(){let t=this.getInt(),e=this.getInts(t);return[t,e]}getSeriesWithExtraData(t){let e=this.getInt(),r=this.getInts(t),n=this.getInts(e);return[[e,...r],n]}getGraphWithAdjList(){let[t,e]=this.getInts(2),r=m(t,()=>[]);for(let n=0,s=e;n<s;++n){let[o,h]=this.getInts(2);r[o-1].push(h-1),r[h-1].push(o-1)}return[t,e,r]}getGraphWithAdjMatrix(){let[t,e]=this.getInts(2),r=m(t,()=>m(t,()=>!1));for(let n=0,s=e;n<s;++n){let[o,h]=this.getInts(2);r[o-1][h-1]=!0,r[h-1][o-1]=!0}return[t,e,r]}getIntPairs(t){let e=[],r=[];for(let n=0,s=t;n<s;++n){let[o,h]=this.getInts(2);e.push(o),r.push(h)}return[e,r]}},N=class extends M{constructor(){super(),(0,A.existsSync)("/dev/stdin")&&(super.data=(0,A.readFileSync)("/dev/stdin","utf-8"))}async setup(){if((0,A.existsSync)("/dev/stdin"))return;let t=[];for await(let n of process.stdin)t.push(n);let r=Buffer.concat(t).toString();super.data=r}};var ct=F(C());var yt=F(j());var m=(i,t)=>{let e=new Array(i);for(let r=0;r<i;++r)e[r]=t(r);return e};var V=Y((i,t)=>t===0?i:()=>V(t,i%t));var D=Y((i,t)=>t===0n?i:()=>D(t,i%t));function Y(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}var q=(i,t)=>i>t?i:t,b=(i,t)=>i<t?i:t;var Et=F(U());var kt=X((i,t)=>{if(t.length===0)return i;let[e,...r]=t;return()=>kt(i[e],r)}),Mt=X((i,t,e)=>{let[r,...n]=t;if(n.length>0)return()=>Mt(i[r],n,e);i[r]=e});function X(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}var E=class{buffer=[];constructor(){}push(t){this.buffer.push(t)}yesNo(t){this.push(t?"Yes":"No")}list(t){this.push(t.join(" "))}lists(t){this.push(t.length);for(let e of t)this.list(e)}listNl(t){for(let e of t)this.push(e)}print(){console.log(this.buffer.join(`
`))}earlyExitTag(){return"earlyExit"}isEarlyExitTag(t){return t==="earlyExit"}};var Z=(i,t)=>i===t;var O=Z;var et=i=>{let t=0,e=0,r=0;for(let n of i)t+=n,e=b(e,t),r=q(r,t-e);return r},rt=i=>{let t=0,e=0,r=0;for(let n of i)t+=n,e=q(e,t),r=b(r,t-e);return r},Ct=(i,t,e)=>{let r=0;for(let n of e)r+=n;if(t>=1){let n=et(e);return BigInt(r)+BigInt(t-1)*BigInt(n)}else{let n=rt(e);return BigInt(r)+BigInt(t-1)*BigInt(n)}},Rt=(i,t)=>{let[e,r]=i.getInts(2),n=i.getInts(e),s=Ct(e,r,n);t.push(s)},tt=new N;tt.setup().then(i=>{let t=new E;try{Rt(tt,t),t.print()}catch(e){if(O(e,"earlyExit"))t.print();else throw e}}).catch(i=>{console.error(i)});0&&(module.exports={maxIntervalSum,minIntervalSum});

Python solution:
#!/usr/bin/env python3
# from typing import *


# def solve(N: int, C: int, A: List[int]) -> int:
def solve(N, C, A):
    total = sum(A)
    tmp = 0
    max_tmp = 0
    l, r = 0, 0
    while r < N: 
        tmp += A[r] if C > 0 else A[r] * -1
        while tmp < 0:
            tmp -= A[l] if C > 0 else A[l] * -1
            l += 1
        max_tmp = max(max_tmp, tmp)
        r += 1
    #     print(l, r, tmp)
    # print(total, max_tmp)
    ans = total + (max_tmp * (C-1)) if C > 0 else total + (max_tmp * (-C+1))
    return ans



# generated by oj-template v4.8.1 (https://github.com/online-judge-tools/template-generator)
def main():
    import sys
    tokens = iter(sys.stdin.read().split())
    N = int(next(tokens))
    C = int(next(tokens))
    A = [None for _ in range(N)]
    for i in range(N):
        A[i] = int(next(tokens))
    assert next(tokens, None) is None
    a = solve(N, C, A)
    print(a)


if __name__ == '__main__':
    main()

Ruby solution:
(N, C), AS = $<.map { _1.chomp.split.map(&:to_i) }

cur = 0
add = 0
AS.each do |a|
  cur = [cur + a * (C - 1), 0].max
  add = cur if add < cur
end

puts AS.sum + add