406109: GYM102268 B Best Subsequence

You have an array $$$w_1, w_2, \ldots, w_n$$$ of length $$$n$$$.

You need to choose a subsequence of $$$k$$$ elements. Let their indices be $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$.

Your goal is to find the minimum possible value of $$$$$$\max \left( (w_{i_1} + w_{i_2}), (w_{i_2} + w_{i_3}), \ldots, (w_{i_{k - 1}} + w_{i_k}), (w_{i_k} + w_{i_1}) \right)$$$$$$ among all such subsequences.

The first line of input contains two integers $$$n$$$ and $$$k$$$: the number of elements in the array $$$w$$$ and the length of subsequence ($$$3 \leq k \leq n \leq 200\,000$$$).

The second line contains $$$n$$$ space-separated integers $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \leq w_i \leq 10^9$$$).

Print one integer: the minimum possible value of $$$$$$\max \left( (w_{i_1} + w_{i_2}), (w_{i_2} + w_{i_3}), \ldots, (w_{i_{k - 1}} + w_{i_k}), (w_{i_k} + w_{i_1}) \right)$$$$$$ among all subsequences of length $$$k$$$.

5 3
17 18 17 30 35

35