AT_arc174_a [ARC174A] A Multiply

[problemUrl]: https://atcoder.jp/contests/arc174/tasks/arc174_a 長さ $ N $ の整数列 $ A=(A_1,A_2,\dots,A_N) $ と整数 $ C $ が与えられます。 以下の操作を **高々 $ 1 $ 度** 行って達成できる $ A $ の全要素の総和の最大値を求めてください。 - $ 1\ \le\ l\ \le\ r\ \le\ N $ を満たす整数 $ l,r $ を指定し、 $ A_l,A_{l+1},\dots,A_r $ の全ての要素を $ C $ 倍する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを整数として出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \le\ N\ \le\ 3\ \times\ 10^5 $ - $ -10^6\ \le\ C\ \le\ 10^6 $ - $ -10^6\ \le\ A_i\ \le\ 10^6 $ ### Sample Explanation 1 この入力では、 $ A=(-10,10,20,30,-20),\ C=2 $ です。 $ l=2,r=4 $ と指定して操作を $ 1 $ 度行うことで、操作後の $ A $ を $ (-10,20,40,60,-20) $ とすることができます。 このとき $ A $ の全要素の総和は $ 90 $ となり、これが達成可能な最大値です。 ### Sample Explanation 2 この入力では、 $ A=(-1,-2,-3,-4,-5),\ C=1000000 $ です。 操作を一度も行わないとき $ A $ の全要素の総和は $ -15 $ となり、これが達成可能な最大値です。