Problem Description

Alisa and Bob became the winners of a TV quiz show, and now they need to choose prizes. There are $n$ prizes, numbered from $1$ to $n$.

The prize selection rules are as follows: The organizer gives a positive integer $k$ ($1 \leq k \leq n / 3$). First, Alisa chooses $k$ consecutive prize indices. Then, Bob chooses $k$ consecutive prize indices, but he cannot choose any index that Alisa has already chosen. After that, the winners receive the prizes they selected.

Alisa knows Bob very well, and she knows how much each prize is worth to Bob (this is a positive integer). Alisa does not like Bob, so when choosing prizes, she wants to make the total value of the prizes Bob chooses as small as possible. Alisa does not care which prizes she gets.

Task: Write a program that, given the prize values and the value of $k$, determines the minimum total value $x$ that Alisa can guarantee, so that the total value of the prizes Bob chooses will not exceed $x$.

Input Format

The first line of the input file contains two integers: $n$ —— the total number of prizes, and $k$ —— the number of consecutive prizes each winner must choose ($3 \leq n \leq 100 000$, $1 \leq k \leq n / 3$).

The second line contains $n$ integers: $a_1, a_2, ..., a_n$, where $a_i$ is the value of the $i$-th prize to Bob ($1 \leq a_i \leq 10^9$).

Output Format

The output file should contain one integer —— the minimum $x$ such that Alisa can make the total value of the prizes Bob chooses not exceed $x$.

10 2
1 2 4 5 2 4 2 2 1 6

7

Hint

Explanation of the Example

In this example, Alisa can choose prizes $4$ and $5$. Then Bob can choose prizes $9$ and $10$, and the total value he gets is $7$.

Scoring System and Subtasks

Subtask 1 (30 points)

$3 \leq n \leq 50$, $1 \leq a_i \leq 10^5$.

Subtask 2 (30 points)

$3 \leq n \leq 5000$, $1 \leq a_i \leq 10^5$.

Subtask 3 (40 points)

$3 \leq n \leq 100 000$, $1 \leq a_i \leq 10^9$.

Translation source: GPT 5.2.

Translated by ChatGPT 5