406109: GYM102268 B Best Subsequence

Memory Limit:0 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Best Subsequencetime limit per test3 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

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.

Input

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$$$).

Output

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$$$.

ExampleInput
5 3
17 18 17 30 35
Output
35

Source/Category

加入题单

上一题 下一题 算法标签: