Selecting Numbers

Interview

Time limit1sMemory limit512 MB

Summary

Choose K numbers from a row so that the sum of each chosen value minus the number of chosen values before it is maximized.

Level: Medium5 of 10
Topics: Dynamic programming, Sorting, Greedy, Prefix sum
Solved: No attempts yet

Problem

N natural numbers are arranged in a row. You must select K of them, all at once.

For each number you select, compute its score. The score is that number minus the count of selected numbers to its left. After computing the score of each selected number, the total score is the sum of those scores. You must select K numbers so that the total score is maximized.

For example, suppose N = 5 natural numbers are given in order as 2 3 1 2 1, and K = 3. If you select the first 2 and the two 1s, the scores of the numbers are 2 0 -1, so the total score is 1. If you select the first 2, the 3, and the second 2, the scores are 2 2 0, so the total score is 4. In this example, the maximum total score is 4.

Given an array of N natural numbers and a positive integer K, write a program that prints the maximum total score.

Input

The first line contains N and K separated by a single space. The second line contains N natural numbers separated by single spaces.

Output

Print, on the first line, the maximum total score obtainable by selecting K of the given N numbers.

Constraints

1 ≤ N ≤ 5 000
1 ≤ K ≤ N
Each given natural number is between 1 and 100 000

Examples2

Example 1
Input
```
5 3
2 3 1 2 1
```
Expected output
```
4
```
Example 2
Input
```
6 2
4 1 5 2 6 3
```
Expected output
```
10
```