Contest Duration: - (local time) (100 minutes) Back to Home
C - Index × A(Continuous ver.) /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• 入力は全て整数。

### 入力

N M
A_1 A_2 \dots A_N


### 入力例 1

4 2
5 4 -1 8


### 出力例 1

15


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) などを選ぶことができないことに注意してください。

### 入力例 2

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


### 出力例 2

31


Score : 300 points

### Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

### Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

### Constraints

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N


### Sample Input 1

4 2
5 4 -1 8


### Sample Output 1

15


When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

### Sample Input 2

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


### Sample Output 2

31