题目描述

在一个遥远的王国，国王希望为他的子民举办一场盛大的宴会。为了确保宴会的成功，他决定从王国的美食书中选择一段连续的菜谱，以最大化宴会的美味指数。

每道菜都有一个独特的美味值，且在宴会上第 $i$ 道被品尝的菜肴会使得其美味值乘以 $i$，从而影响整体的美味指数。

国王需要选择一段长度为 $M$ 的连续菜谱，使得美味指数 $\displaystyle \sum_{i=1}^{M} i \times B_i$ 达到最大，其中 $B=(B_1,B_2,\dots,B_M)$ 表示所选的连续菜谱。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示美食书中菜谱的总数和国王希望选择的连续菜谱的长度。

第二行包含 $N$ 个整数，表示每道菜的美味值。

输出格式

输出一个整数，表示所能获得的最大美味指数。

样例

5 3
1 -2 3 -1 5

16

数据范围

• $1 \le M \le N \le 2 \times 10^5$
• $-2 \times 10^5 \le A_i \le 2 \times 10^5$
• 输入中的所有值均为整数。