시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 4 2 2 100.000%

문제

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.

예제 입력 1

5 3
17 18 17 30 35

예제 출력 1

35

출처

Camp > Petrozavodsk Programming Camp > Winter 2019 > Day 1 B번

  • 문제를 만든 사람: 300iq