There are $n$ bulbs in a straight line, numbered from $\mbox{0}$ to $n-1$. 
Each bulb $\boldsymbol{i}$ has a button associated with it, and there is a cost, $c_i$, for pressing this button. When some button $\boldsymbol{i}$ is pressed, all the bulbs at a distance $\leq k$ from bulb $\boldsymbol{i}$ will be toggled(off->on, on->off). 

Given $n$, $\boldsymbol{\mbox{k}}$, and the costs for each button, find and print the minimum cost of turning off all $n$ bulbs if they're all on initially.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $\boldsymbol{\mbox{k}}$. 

The second line contains $n$ space-separated integers describing the respective costs of each bulb (i.e., $c_0,c_1,\ldots,c_{n-1}$).

Constraints

$3\leq n\leq10^4$
$0\leq k\leq1000$
$0\leq c_i\leq10^9$

Output Format

Print a long integer denoting the minimum cost of turning off all $n$ bulbs.

Sample Input
3 1
1 1 1

Sample Output
1

Explanation

If we press the middle switch, the middle bulb and the $k=1$ closest adjacent bulbs (i.e., the first and third) will turn off. Because all bulbs will be off in one button press, this cost is minimal. Thus, we print $1$ as our answer.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(n, k) = map(int, input().split(' '))
c = list(map(int, input().split(' ')))
cost = 10000 * 1000000000
step = 2 * k + 1
if k == 0:
	ans = 0
	for i in c:
		ans += i
	print(ans)
else:
	for start in range(0, k + 1):
		remain = (n - 1 - start - k) % step
		if remain == 0 or remain > k:
			tmp_cost = 0
			for i in range(start, n + 1, step):
				tmp_cost += c[i]
				if tmp_cost > cost:
					break
			if tmp_cost < cost:
				cost = tmp_cost
	print(cost)


def findBest(numList, k):
	leastCost = 2 ** 60
	n = len(numList)
	for i in range(k + 1):
		if i >= n:
			break
		if (n - 1 - i) % (2 * k + 1) > k:
			continue
		currSum = 0
		for j in range(i, n, 2 * k + 1):
			currSum += numList[j]
		leastCost = min(leastCost, currSum)
	return leastCost
(n, k) = list(map(int, input().split()))
numList = list(map(int, input().split()))
print(findBest(numList, k))


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
m = 100000000000000000
for i in range(k + 1):
	p = i
	if i >= n:
		break
	sum = a[i]
	while True:
		if p + k + 1 >= n:
			m = min(m, sum)
			break
		if p + 2 * k + 1 >= n:
			break
		p = p + 2 * k + 1
		sum = sum + a[p]
print(m)


def findBest(numList, k):
	leastCost = 2 ** 60
	n = len(numList)
	for i in range(k + 1):
		if i >= n:
			break
		if (n - 1 - i) % (2 * k + 1) > k:
			continue
		currSum = 0
		for j in range(i, n, 2 * k + 1):
			currSum += numList[j]
		leastCost = min(leastCost, currSum)
	return leastCost
(n, k) = list(map(int, input().split()))
numList = list(map(int, input().split()))
print(findBest(numList, k))


(n, k) = list(map(int, input().strip().split(' ')))
c = list(map(int, input().strip().split(' ')))
cycle = 2 * k + 1
noidx = [(n + i) % cycle for i in range(1, k + 1)]
idx = []
for i in range(1, k + 2):
	if i not in noidx:
		idx.append(i)
start = 0
costs = len(idx) * [0]
while start < n:
	for i in range(len(idx)):
		bulb = start + idx[i] - 1
		if bulb >= n:
			break
		costs[i] += c[bulb]
	start += cycle
print(min(costs))


(N, K) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
ans = 9999999999
for i in range(K + 1):
	current_bulb = i
	cost = 0
	while current_bulb < N:
		cost += arr[current_bulb]
		current_bulb += 2 * K + 1
	current_bulb = current_bulb - 2 * K - 1
	if current_bulb + K >= N - 1:
		ans = ans if ans < cost else cost
print(ans)


(N, K) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
ans = 9999999999
for i in range(K + 1):
	current_bulb = i
	cost = 0
	while current_bulb < N:
		cost += arr[current_bulb]
		current_bulb += 2 * K + 1
	current_bulb = current_bulb - 2 * K - 1
	if current_bulb + K >= N - 1:
		ans = ans if ans < cost else cost
print(ans)


nk = input().split()
n = int(nk[0])
k = int(nk[1])
c = list(map(int, input().rstrip().split()))
l = 2 * k + 1
res = 10 ** 16
for i in range(k + 1):
	j = i
	a = 0
	while j < n:
		a += c[j]
		j += l
	if j - l + k + 1 >= n:
		res = min(res, a)
print(res)


(n, k) = map(int, input().split())
c = list(map(int, input().split()))
l = 2 * k + 1
res = 10 ** 16
for i in range(k + 1):
	j = i
	a = 0
	while j < n:
		a += c[j]
		j += l
	if j - l + k + 1 >= n:
		res = min(res, a)
print(res)