{"raw_statement":[{"iden":"problem statement","content":"You are given an integer sequence of length $N$, $A=(A_1,A_2,\\dots,A_N)$, and an integer $C$.  \nFind the maximum possible sum of the elements in $A$ after performing the following operation **at most once**:\n\n*   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$."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\le N \\le 3 \\times 10^5$\n*   $-10^6 \\le C \\le 10^6$\n*   $-10^6 \\le A_i \\le 10^6$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $C$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"5 2\n-10 10 20 30 -20"},{"iden":"sample output 1","content":"90\n\nIn this input, $A=(-10,10,20,30,-20), C=2$.  \nAfter performing the operation once specifying $l=2$ and $r=4$, $A$ will be $(-10,20,40,60,-20)$.  \nHere, the sum of the elements in $A$ is $90$, which is the maximum value achievable."},{"iden":"sample input 2","content":"5 1000000\n-1 -2 -3 -4 -5"},{"iden":"sample output 2","content":"\\-15\n\nIn this input, $A=(-1,-2,-3,-4,-5), C=1000000$.  \nWithout performing the operation, the sum of the elements in $A$ is $-15$, which is the maximum value achievable."},{"iden":"sample input 3","content":"9 -1\n-9 9 -8 2 -4 4 -3 5 -3"},{"iden":"sample output 3","content":"13"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}