상품

앨리스와 밥은 텔레비전 퀴즈 쇼의 우승자가 되었고, 이제 상품을 골라야 한다. 고를 수 있는 상품은 1번부터 n번까지 번호가 붙은 n개이다.

상품 분배는 다음과 같이 진행된다. 퀴즈 쇼 주최측은 우승자들에게 양의 정수 k(1 ≤ k ≤ n / 3)를 알려준다. 먼저 앨리스가 연속한 k개의 상품 번호를 고른다. 그다음 밥이 연속한 k개의 상품 번호를 고르는데, 앨리스가 이미 고른 번호는 고를 수 없다. 그 후 우승자들은 자신이 고른 상품을 가져간다.

앨리스는 밥을 잘 알고 있어서, 각 상품이 밥에게 얼마나 가치 있는지 알아냈다. 그 값은 양의 정수이다. 앨리스는 밥에게 화가 나서, 밥이 가져갈 상품의 가치 합이 최대한 작아지도록 자신의 상품을 고르려 한다. 앨리스는 자신이 어떤 상품을 받는지는 신경 쓰지 않는다.

상품의 가치 정보와 k가 주어졌을 때, 앨리스가 밥이 가치 합이 x보다 큰 상품을 고르지 못하게 만들 수 있는 최소 x를 구하는 프로그램을 작성하시오.

첫째 줄에는 두 정수 n과 k가 주어진다. n은 전체 상품의 수이고, k는 두 우승자가 각각 골라야 하는 연속한 상품 번호의 개수이다(3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3).

둘째 줄에는 n개의 양의 정수 a1, a2, …, an이 주어진다. 각 상품이 밥에게 가지는 가치이다(1 ≤ ai ≤ 109).

앨리스가 밥이 가치 합이 x보다 큰 상품을 고르지 못하게 만들 수 있는 최소 x를 한 줄에 출력한다.

예시에서 앨리스는 4번과 5번 상품을 고를 수 있다. 그러면 밥에게는 가치 합이 7인 9번과 10번 상품을 고르는 것이 최선이다.