Description

给定一个长度为 $n$ 的数组 $A$，求一个长度为 $m$ 的的子数组 $B$（无需连续），使得$\sum\limits_{i=1} ^{m}(i * B[i])$最大。输出这个最大值。

Format

Input

第一行为空格隔开的两个整数 $N$ 和 $M$

第二行有 $N$ 个空格隔开的整数，表示 $A_i$

Output

打印答案

Samples

4 2
5 4 -1 8

21

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

54

Limitation

• $1≤M≤N≤2×10^3$
• -$2 \times 10^5 \le A_i \le 2 \times 10^5$
• 输入的值为整数