Cute_Subsequences — OOI final
Task type: batch | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 16
Algorithms: data structures, dynamic programming

# Cute Subsequences

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1 second        |
| Memory limit: | 256 megabytes   |

You are given an array of $n$ positive integers $a_1, a_2, ..., a_n$, as well as a positive integer $k$. You need to divide the array into $k$ non-empty subsequences such that each element of the array belongs to exactly one subsequence. A subsequence is a sequence that can be obtained from another sequence by deleting some elements without changing the order of the remaining elements.

Let the $i$-th subsequence contain elements with indices $j_1 < ... < j_l$. The value of this subsequence is defined as the maximum value of $a_{j_m} + m$ for all $m$ from 1 to $l$.

The cost of dividing the array into $k$ subsequences is the sum of the values of these subsequences.

Find the maximum cost of the division.

### Input

The first line contains two positive integers $n$ and $k$ $(1 \le k \le n \le 500\,000)$ — the size of the array and the number of subsequences to divide it into.

The second line contains $n$ positive integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ — the elements of the array.

### Output

Output the maximum cost of dividing the given array into $k$ non-empty subsequences.

### Example

| standard input | standard output |
|----------------|-----------------|
| 5 3<br>3 7 10 1 2| 24              |

### Note

In the sample test, the array can be divided into [3, 10], [7], [1, 2]. Then the answer will be (10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24.

### Scoring

The tests for this problem consist of six groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed.

| Group | Points | Additional Constraints | Required Groups | Comment               |
|-------|--------|-----------------------|-----------------|-----------------------|
|       |        | $n$                     | $k$               |                     |
| 0     | 0      | -                     | -               | -                     | Examples.             |
| 1     | 14     | $n \le 8$              | -               | 0                     |                       |
| 2     | 19     | -                     | $k = 2$          | -                     |                       |
| 3     | 17     | -                     | -               | -                     | $a_{i+1} \le a_i$     |
| 4     | 21     | -                     | -               | -                     | $a_{i+1} \ge a_i - 1$ |
| 5     | 15     | $n \le 1000$          | -               | 0, 1                  |                       |
| 6     | 14     | -                     | -               | 0 – 5                 |                       |

Starter code: