You are given an array A of N integers and an integer K.

Select a subsequence of exactly K elements from the array while preserving their original order.

If the selected elements are B1, B2, ..., BK, then the score of the subsequence is

[ \sum_{i=1}^{K} i \times B_i ]

Find the maximum possible score.

Input

The first line contains two integers N and K.

The second line contains N integers A1, A2, ..., AN.

Output

Print the maximum possible score.

Constraints

• 1 ≤ K ≤ N ≤ 3000
• -10^9 ≤ Ai ≤ 10^9

Example

Input

5 3
3 5 2 6 4

Output

29

Explanation

Choose the subsequence [5, 6, 4].

Score

1×5 + 2×6 + 3×4
= 5 + 12 + 12
= 29

---