Maximizing Account Safety Index

In this problem, you are given an integer n and another integer k along with an array a of length n. Each element a_i represents the safety index of the i-th post. The posts have to be partitioned into exactly k contiguous segments (each segment corresponds to one account). For each segment, the safety index of an account is defined as the safety value of the first post in that segment. However, if an account is used to post two consecutive posts, its safety index is reduced by the minimum of the safety indices of these two posts.

You need to partition the posts so that the sum of all accounts' safety indices is maximized. Formally, if you partition the indices 1 through n into exactly k contiguous segments S₁, S₂, \dots, S_k (with each segment non-empty) and let the first post in segment S_i be at index f_i, then the objective is to maximize:

[ \Bigl(\sum_{i=1}^{k}a_{f_i}\Bigr) - \Bigl(\sum_{i=1}^{n-1}\min(a_i,a_{i+1})\cdot[,d_i=d_{i+1},]\Bigr), ]

where [d_i=d_{i+1}] equals 1 if posts i and i+1 are in the same segment (i.e. posted using the same account) and 0 otherwise. All formulas are in \(\LaTeX\) format.

Hint: Notice that if the posts were all made by a single account, the total safety would be:

[ \text{base} = a_1 - \sum_{i=1}^{n-1}\min(a_i,a_{i+1}). ]

Now, if you decide to break between posts i and i+1, the penalty between these posts is removed, and you add a new account whose safety value is a_i+1. Thus, such a split gives an extra benefit of:

[ a_{i+1} + \min(a_i,a_{i+1}). ]

Your goal is to choose exactly k-1 split positions (from the n-1 possible) to maximize the sum of the extra benefits plus the base value. Equivalently, compute the answer as:

[ \text{answer} = \left(a_1 - \sum_{i=1}^{n-1}\min(a_i,a_{i+1})\right) + \sum_{j=1}^{k-1} \Delta_j, ]

where \(\Delta_j\) are the top k-1 values among \(a_{i+1} + \min(a_i,a_{i+1})\) for i = 1, 2, \dots, n-1.

inputFormat

The first line contains two integers n and k separated by a space.

The second line contains n space-separated integers representing the array a.

Constraints: \(1 \le k \le n \le 10^5\) and \(1 \le a_i \le 10^9\).

outputFormat

Output a single integer — the maximum achievable sum of safety indices.

sample

5 2
5 3 4 2 6

3