Best Subsequence

배열에서 인덱스 순서를 유지하며 k개를 골라 인접한 원소끼리의 합의 최댓값을 최소로 만드는데, 마지막 원소는 첫 원소와도 짝을 이룬다.

어려움8이분 탐색그리디정렬배열아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제 설명

예제1

You have an array w1, w2, . . . , wn of length n.

You need to choose a subsequence of k elements. Let their indices be 1 ≤ i1 < i2 < . . . < ik ≤ n.

Your goal is to find the minimum possible value of

max ((wi1 + wi2),(wi2 + wi3), . . . ,(wik−1 + wik),(wik + wi1))

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 w1, w2, . . . , wn (1 ≤ wi ≤ 109).

Print one integer: the minimum possible value of

max ((wi1 + wi2),(wi2 + wi3), . . . ,(wik−1 + wik),(wik + wi1))

among all subsequences of length k.