18448번 - Best Subsequence 다국어

You have an array w₁, w₂, . . . , w_n of length n.

You need to choose a subsequence of k elements. Let their indices be 1 ≤ i₁ < i₂ < . . . < i_k ≤ n.

Your goal is to find the minimum possible value of

max ((w_i1 + w_i2),(w_i2 + w_i3), . . . ,(w_ik−1 + w_ik),(w_ik + w_i1))

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 ≤ k ≤ n ≤ 200 000).

The second line contains n space-separated integers w₁, w₂, . . . , w_n (1 ≤ w_i ≤ 10⁹).

Print one integer: the minimum possible value of

max ((w_i1 + w_i2),(w_i2 + w_i3), . . . ,(w_ik−1 + w_ik),(w_ik + w_i1))

among all subsequences of length k.