AT_abc267_c [ABC267C] Index × A(Continuous ver.)

[problemUrl]: https://atcoder.jp/contests/abc267/tasks/abc267_c 長さ $ N $ の整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 長さ $ M $ の $ A $ の連続部分列 $ B=(B_1,B_2,\dots,B_M) $ に対する、$ \displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i $ の最大値を求めてください。

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

答えを出力せよ。

### 注記 数列の**連続部分列**とは、数列の先頭から $ 0 $ 個以上、末尾から $ 0 $ 個以上の要素を削除して得られる列のことをいいます。 例えば $ (2,\ 3) $ や $ (1,\ 2,\ 3) $ は $ (1,\ 2,\ 3,\ 4) $ の連続部分列ですが、$ (1,\ 3) $ や $ (3,2,1) $ は $ (1,\ 2,\ 3,\ 4) $ の連続部分列ではありません。 ### 制約 - $ 1\ \le\ M\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ -\ 2\ \times\ 10^5\ \le\ A_i\ \le\ 2\ \times\ 10^5 $ - 入力は全て整数。 ### Sample Explanation 1 $ B=(A_3,A_4) $ とした場合、$ \displaystyle\ \sum_{i=1}^{M}\ i\ \times\ B_i\ =\ 1\ \times\ (-1)\ +\ 2\ \times\ 8\ =\ 15 $ となります。$ 16 $ 以上の値を達成することはできないため、解は $ 15 $ です。 $ B=(A_1,A_4) $ などを選ぶことができないことに注意してください。