The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $n$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $i$-th picture has beauty $a_i$.

Vova wants to repost exactly $x$ pictures in such a way that:   each segment of the news feed of at least $k$ consecutive pictures has at least one picture reposted by Vova;  the sum of beauty values of reposted pictures is maximum possible. 

For example, if $k=1$ then Vova has to repost all the pictures in the news feed. If $k=2$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.


-----Input-----

The first line of the input contains three integers $n, k$ and $x$ ($1 \le k, x \le n \le 200$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the beauty of the $i$-th picture.


-----Output-----

Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.


-----Examples-----
Input
5 2 3
5 1 3 10 1

Output
18

Input
6 1 5
10 30 30 70 10 10

Output
-1

Input
4 3 1
1 100 1 1

Output
100

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
from math import *
from collections import deque

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	(n, k, x) = mints()
	a = list(mints())
	d = [-1e+50] * n
	p = [-1e+50] * n
	for i in range(0, k):
		d[i] = a[i]
	q = deque()
	for xx in range(1, x):
		(d, p) = (p, d)
		q.clear()
		for nn in range(xx - 1, n):
			while len(q) != 0 and q[0][1] < nn - k:
				q.popleft()
			if len(q):
				d[nn] = q[0][0] + a[nn]
			else:
				d[nn] = -1e+50
			while len(q) and q[-1][0] <= p[nn]:
				q.pop()
			q.append((p[nn], nn))
	m = -1
	for i in range(n - k, n):
		m = max(m, d[i])
	print(m)
solve()


from functools import lru_cache
(n, k, x) = list(map(int, input().split()))
arr = list(map(int, input().split()))

@lru_cache(maxsize=50000)
def dp(i, y):
	if i >= 0 and i < k and (y == 0):
		return 0
	elif i < 0 or y <= 0:
		return -1000000000001
	return max((dp(i - delta - 1, y - 1) + arr[i - delta - 1] for delta in range(min(k, i + 1))))
print(max(dp(n, x), -1))


(n, k, x) = list(map(int, input().split()))
a = [None] + list(map(int, input().split()))
dp = [[-1] * (n + 1) for i in range(x + 1)]
dp[0][0] = 0
for i in range(1, x + 1):
	for j in range(1, n + 1):
		dp[i][j] = max((dp[i - 1][j2] for j2 in range(max(0, j - k), j)))
		if dp[i][j] != -1:
			dp[i][j] += a[j]
ans = max((dp[x][j] for j in range(n - k + 1, n + 1)))
print(ans)


import sys
S = sys.stdin.read()
S = list([list(map(int, x)) for x in list([x.split() for x in [x for x in S.split('\n') if len(x) > 1]])])
(n, k, x, B) = (S[0][0], S[0][1], S[0][2], S[1])
X = [[-1 for i in range(x + 1)] for i in range(n + 1)]
X[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, x + 1):
		X[i][j] = max([X[i][j], max([-1] + [X[i - l][j - 1] + B[i - 1] for l in range(1, min([i, k]) + 1) if X[i - l][j - 1] != -1])])
print(max(list(map(max, X[n - k + 1:n + 1]))))


(n, k, x) = map(int, input().split())
a = [None] + list(map(int, input().split()))
(lo, hi) = (0, 10 ** 9 * 5000)
q = [None] * (n + 1)

def get(mid):
	(f, r) = (0, 0)
	q[0] = (0, 0, 0)
	for i in range(1, n + 1):
		if q[r][2] == i - k - 1:
			r += 1
		cur = (q[r][0] + a[i] - mid, q[r][1] + 1, i)
		while r <= f and q[f] <= cur:
			f -= 1
		f += 1
		q[f] = cur
	if q[r][2] == n - k:
		r += 1
	return q[r]
while lo < hi:
	mid = lo + hi + 1 >> 1
	(_, cnt, _) = get(mid)
	if cnt >= x:
		lo = mid
	else:
		hi = mid - 1
(sm, _, _) = get(lo)
ans = max(-1, sm + x * lo)
print(ans)


import os, sys
from io import BytesIO, IOBase

def main():
	inf = -10 ** 20
	(n, K, x) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = [[[inf] * K for _ in range(x + 1)] for _ in range(n)]
	for i in range(K):
		dp[i][1][0] = a[i]
	for i in range(n - 1):
		for j in range(x + 1):
			for k in range(K):
				if j != x:
					dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0], dp[i][j][k] + a[i + 1])
				if k != K - 1:
					dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k])
	ans = max(dp[n - 1][x])
	print(ans if ans > 0 else -1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
(N, K, X) = MAP()
A = [0] + LIST()
dp = list2d(X + 1, N + 1, -1)
dp[0][0] = 0
for i in range(X):
	for j in range(N):
		if dp[i][j] == -1:
			continue
		for k in range(j + 1, min(j + K + 1, N + 1)):
			dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + A[k])
ans = max(dp[X][-K:])
print(ans)


from math import ceil
(n, jump, count) = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [[-1] * (count + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(count):
		if dp[i][j] >= 0:
			for k in range(1, min(jump, n - i) + 1):
				dp[i + k][j + 1] = max(dp[i + k][j + 1], dp[i][j] + a[i + k])
ans = 0
for i in range(n - jump + 1, n + 1):
	ans = max(ans, dp[i][count])
if n // jump > count:
	print(-1)
else:
	print(ans)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
(n, k, x) = mints()
a = list(mints())
d = [None] * (n + 1)
p = [None] * (n + 1)
for i in range(0, k):
	d[i] = a[i]
for xx in range(2, x + 1):
	(d, p) = (p, d)
	for nn in range(n):
		m = None
		for i in range(max(0, nn - k), nn):
			if p[i] != None:
				if m == None:
					m = p[i]
				else:
					m = max(m, p[i])
		if m != None:
			d[nn] = m + a[nn]
		else:
			d[nn] = None
m = -1
for i in range(n - k, n):
	if d[i] != None:
		m = max(m, d[i])
print(m)


import sys
input = sys.stdin.readline
(n, k, x) = map(int, input().split())
a = list(map(int, input().split()))
dp = [-1] * (n + 1)
dp[0] = 0
for c in range(1, x + 1):
	dp0 = [-1] * (n + 1)
	for i in range(c, n + 1):
		ma = -1
		for j in range(1, min(i, k) + 1):
			ma = max(ma, dp[i - j])
		if ma == -1:
			break
		dp0[i] = ma + a[i - 1]
	dp = dp0
ans = -1
for i in range(k):
	ans = max(ans, dp[n - i])
print(ans)


import math
import collections
import bisect
import heapq
import time
import itertools
import sys
(N, K, X) = map(int, input().split())
A = [0] + [int(x) for x in input().split()]
dp = [[float('-inf') for _ in range(X + 1)] for _ in range(N + 1)]
dp[0][X] = 0
for i in range(1, N + 1):
	for x in range(X):
		for p in range(1, K + 1):
			if i - p < 0:
				break
			if dp[i - p][x + 1] < 0:
				continue
			dp[i][x] = max(dp[i][x], dp[i - p][x + 1] + A[i])
ans = max([max(v) for v in dp[N - K + 1:]])
if ans < 0:
	print(-1)
else:
	print(ans)


(N, K, X) = list(map(int, input().split()))
arr = [0] + [int(i) for i in input().split()]
dp = [[float('-inf') for _ in range(X + 1)] for _ in range(N + 1)]
dp[0][X] = 0
for i in range(1, N + 1):
	for x in range(X):
		for p in range(1, K + 1):
			if i - p < 0:
				break
			if dp[i - p][x + 1] < 0:
				continue
			dp[i][x] = max(dp[i][x], dp[i - p][x + 1] + arr[i])
ans = max([max(v) for v in dp[N - K + 1:]])
if ans < 0:
	print(-1)
else:
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, k, x) = RL()
	arr = RLL()
	dp = [[-1] * (x + 1) for _ in range(n + 1)]
	dp[0][0] = 0
	res = -1
	for i in range(1, n + 1):
		for j in range(x + 1):
			for l in range(i - 1, max(i - 1 - k, -1), -1):
				if dp[l][j - 1] == -1:
					continue
				if j - 1 >= 0:
					dp[i][j] = max(dp[l][j - 1] + arr[i - 1], dp[i][j])
					if n - i < k:
						res = max(res, dp[i][j])
	print(res)
main()


from sys import stdin, stdout
import collections
(N, K, X) = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
if X < N // K:
	print(-1)
	quit()
dp = [[0] * N for _ in range(X)]
for i in range(K):
	dp[0][i] = arr[i]
for i in range(X - 1):
	for j in range(N):
		if dp[i][j] != 0:
			for z in range(j + 1, min(j + K + 1, N)):
				dp[i + 1][z] = max(dp[i + 1][z], dp[i][j] + arr[z])
res = 0
for i in range(N - K, N):
	res = max(res, dp[X - 1][i])
print(res)


from math import inf
(n, k, x) = map(int, input().split())
a = [int(x) for x in input().split()]
dp = [[-inf] * (x + 1) for i in range(n + 1)]
dp[0][x] = 0
for i in range(1, n + 1):
	for j in range(x):
		for p in range(1, k + 1):
			if i >= p:
				dp[i][j] = max(dp[i][j], dp[i - p][j + 1] + a[i - 1])
an = -1
for i in range(n - k + 1, n + 1):
	an = max(an, max(dp[i]))
if an != -1:
	print(an)
else:
	print(-1)