F. Alarm Clocks

You are given two arrays $a$ and $b$ of length $n$. Initially $a_i = 5 dot.op 10^5 + 1$ and $1 <= b_i <= 5 dot.op 10^5$ holds for every $i$ from $1$ to $n$. Additionally, you are given a non-negative integer $k$ such that $2 k + 1 <= n$. You can make some operations on the array $a$. In an operation, you can select two positive integers $x, v$ such that $k + 1 <= x <= n -k$, $1 <= v <= 5 dot.op 10^5$, and set $a_i$ to $min (a_i, v)$ for every $i$ from $x -k$ to $x + k$. After performing some operations, you hope $a_i <= b_i$ holds for every $i$ from $1$ to $n$, but you would like to maximize the sum of all elements in $a$ at the same time. What is the maximum possible sum you can achieve after performing some operations? The first line contains two integers $n, k$ ($1 <= n <= 3000$, $k >= 0$, $2 k + 1 <= n$). The second line contain $n$ integers $b_1, b_2, \\\\cdots, b_n$ ($1 <= b_i <= 5 dot.op 10^5$). Print an integer — The maximum possible sum of all elements in $a$. ## Input The first line contains two integers $n, k$ ($1 <= n <= 3000$, $k >= 0$, $2 k + 1 <= n$).The second line contain $n$ integers $b_1, b_2, \\\\cdots, b_n$ ($1 <= b_i <= 5 dot.op 10^5$). ## Output Print an integer — The maximum possible sum of all elements in $a$. [samples] ## Scoring Subtask 1 (7 points): $forall 1 <= i < n$, $a_i <= a_{i + 1}$. Subtask 2 (14 points): $1 <= a_i <= 2$. Subtask 3 (16 points): $1 <= n <= 100$. Subtask 4 (24 points): $1 <= n <= 500$. Subtask 5 (39 points): No additional constraints.