F. Alarm Clocks
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Initially $$$a_i = 5 \cdot 10^5 + 1$$$ and $$$1 \leq b_i \leq 5 \cdot 10^5$$$ holds for every $$$i$$$ from $$$1$$$ to $$$n$$$. Additionally, you are given a non-negative integer $$$k$$$ such that $$$2k+1 \leq 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 \leq x \leq n-k$$$, $$$1 \leq v \leq 5 \cdot 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 \leq 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?

Input

The first line contains two integers $$$n, k$$$ ($$$1 \leq n \leq 3000$$$, $$$k \geq 0$$$, $$$2k+1 \leq n$$$).

The second line contain $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^5$$$).

Output

Print an integer — The maximum possible sum of all elements in $$$a$$$.

Scoring
  • Subtask 1 (7 points): $$$\forall 1 \leq i \lt n$$$, $$$a_i \leq a_{i+1}$$$.
  • Subtask 2 (14 points): $$$1 \leq a_i \leq 2$$$.
  • Subtask 3 (16 points): $$$1 \leq n \leq 100$$$.
  • Subtask 4 (24 points): $$$1 \leq n \leq 500$$$.
  • Subtask 5 (39 points): No additional constraints.
Examples
Input
5 1
3 1 2 5 4
Output
11
Input
1 0
12
Output
12
Input
16 3
10 2 17 26 2 23 31 13 9 21 4 4 12 13 19 10
Output
80