Maximizing Account Safety Sum

Little A wants to post n posts on Codeforces using k newly registered accounts. He must post in the order from 1 to n and use all k accounts.

However, if the same account posts two consecutive posts, it will be immediately banned. To avoid this, Little A decides that the safety index of an account is defined as the safety index of the post where this account is first used. Each post i carries a safety value a_i (which represents the probability of not being banned after that post).

Formally, you are given a sequence of n posts with corresponding safety indices a₁, a₂, ..., a_n. You are to partition the posts (i.e. the indices 1 to n) into exactly k nonempty subsets S₁, S₂, ..., S_k such that for any two consecutive posts, they are assigned to different accounts. For each account, its safety index is defined as a[\min\{ j \in S_i \}] and the goal is to maximize the sum:

$$\sum_{i=1}^{k} a\Bigl[\min_{j \in S_i} j\Bigr]$$

It is guaranteed that the posting order forces account 1 to be used in the first post, and for any subsequent post, if only one account has been used so far, a new account must be introduced to avoid consecutive usage.

Your task is to compute the maximum possible sum of the safety indices over all k accounts.

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n).

The second line contains n integers: a₁, a₂, ..., a_n (each a_i is the safety index of the i-th post).

You may assume that the input always admits a valid assignment according to the problem statement.

outputFormat

Output a single integer, which is the maximum total safety sum achievable.

sample

1 1
10

10