You are a coach at your local university. There are $n$ students under your supervision, the programming skill of the $i$-th student is $a_i$.

You have to form $k$ teams for yet another new programming competition. As you know, the more students are involved in competition the more probable the victory of your university is! So you have to form no more than $k$ (and at least one) non-empty teams so that the total number of students in them is maximized. But you also know that each team should be balanced. It means that the programming skill of each pair of students in each team should differ by no more than $5$. Teams are independent from one another (it means that the difference between programming skills of two students from two different teams does not matter).

It is possible that some students not be included in any team at all.

Your task is to report the maximum possible total number of students in no more than $k$ (and at least one) non-empty balanced teams.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 5000$) — the number of students and the maximum number of teams, correspondingly.

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 a programming skill of the $i$-th student.


-----Output-----

Print one integer — the maximum possible total number of students in no more than $k$ (and at least one) non-empty balanced teams.


-----Examples-----
Input
5 2
1 2 15 15 15

Output
5

Input
6 1
36 4 1 25 9 16

Output
2

Input
4 4
1 10 100 1000

Output
4

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Amortized analysis
Skill types: Dynamic programming

Sorting

Amortized analysis

Starter code:

Solutions:
(n, k) = list(map(int, input().split()))
a = sorted((int(i) for i in input().split()))
u = [0] * n
(i, j) = (0, 0)
while j < n:
	if a[i] + 5 >= a[j]:
		j += 1
	else:
		i += 1
	u[i] = j
dp = [[0] * (k + 1) for i in range(n + 1)]
for i in range(n - 1, -1, -1):
	for j in range(1, k + 1):
		x = u[i]
		dp[i][j] = max(1 + dp[i + 1][j - 1], dp[i + 1][j], x - i + dp[x][j - 1])
print(dp[0][k])


import bisect
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
DP = [[0] * (k + 1) for i in range(n)]
for i in range(n):
	x = bisect.bisect_right(A, A[i] + 5) - 1
	for j in range(k - 1, -1, -1):
		DP[i][j] = max(DP[i][j], DP[i - 1][j])
		DP[x][j + 1] = max(DP[i - 1][j] + x - i + 1, DP[x][j + 1])
print(max([DP[i][-1] for i in range(n)]))


(n, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
i = 0
j = 0
ans = 0
start = [0] * n
for _ in range(n):
	while j < i and a[i] - a[j] > 5:
		j += 1
	start[i] = j
	i += 1
dp = [[0] * (k + 1) for _ in range(n)]
for i in range(1, k + 1):
	dp[0][i] = 1
for i in range(1, n):
	for j in range(1, k + 1):
		lastgroup = 0
		if start[i] >= 1:
			lastgroup = dp[start[i] - 1][j - 1]
		dp[i][j] = max(dp[i - 1][j], lastgroup + (i - start[i]) + 1)
print(dp[-1][-1])


def main():
	(n, k) = list(map(int, input().split()))
	a = sorted((int(i) for i in input().split()))
	upper_bound = [0] * n
	(i, j) = (0, 0)
	while j < n:
		if a[i] + 5 >= a[j]:
			j += 1
		else:
			i += 1
		upper_bound[i] = j
	dp = [[0] * (k + 1) for _ in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(1, k + 1):
			x = upper_bound[i]
			dp[i][j] = max(1 + dp[i + 1][j - 1], dp[i + 1][j], x - i + dp[x][j - 1])
	print(dp[0][k])

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
cnti = [0 for i in range(n)]
for i in range(n):
	count = 0
	for j in range(i, n):
		if arr[j] - arr[i] <= 5:
			count += 1
			continue
		break
	cnti[i] = count
dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
for i in range(n):
	for j in range(k + 1):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if j < k:
			dp[i + cnti[i]][j + 1] = max(dp[i + cnti[i]][j + 1], dp[i][j] + cnti[i])
print(dp[n][k])


import io
import os
import sys

def main():
	(n, k) = list(map(int, input().split()))
	a = sorted(list(map(int, input().split())))
	maxFromI = [0] * n
	end = -1
	for i in range(n):
		while end + 1 < n and a[end + 1] <= a[i] + 5:
			end += 1
		maxFromI[i] = end - i + 1
	dp = [[0] * (k + 1) for _ in range(n + 1)]
	for i in range(n):
		for j in range(k + 1):
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
			if j + 1 <= k:
				dp[i + maxFromI[i]][j + 1] = max(dp[i + maxFromI[i]][j + 1], dp[i][j] + maxFromI[i])
	print(dp[n][k])

def __starting_point():
	main()
__starting_point()


import os
import sys
from io import BytesIO, IOBase
from array import array

def main():
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	dp = [array('i', [0] * (k + 1)) for _ in range(n + 1)]
	l = 1
	for i in range(1, n + 1):
		while l < n + 1 and a[l - 1] - a[i - 1] <= 5:
			for j in range(1, k + 1):
				dp[l][j] = max(dp[l][j], dp[l - 1][j], dp[i - 1][j - 1] + l - i + 1)
			l += 1
	print(max((max(i) for i in dp)))
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 os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
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')
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
dp = [0] * n
start = a[0]
(k, i) = (0, 0)
while i < n:
	if a[i] - start > 5:
		dp[k] = i - k
		k += 1
		start = a[k]
	else:
		i += 1
dp[k] = n - k
for i in range(k + 1, n):
	dp[i] = dp[i - 1] - 1
if dp[0] == n:
	print(n)
	exit()
dp2 = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n - 1, -1, -1):
	for j in range(1, m + 1):
		dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j - 1] + 1, dp2[dp[i] + i][j - 1] + dp[i])
print(dp2[0][m])


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l = r = 0
b = [0] * n
for _ in range(n):
	while l < r and a[r] - a[l] > 5:
		l += 1
	b[r] = l
	r += 1
dp = [[0 for _ in range(k + 1)] for _ in range(n)]
for i in range(1, k + 1):
	dp[0][i] = 1
for i in range(1, n):
	for j in range(1, k + 1):
		dp[i][j] = max(dp[i - 1][j], (dp[b[i] - 1][j - 1] if b[i] >= 1 else 0) + (i - b[i] + 1))
print(dp[-1][-1])


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = [0] * n
for i in range(n):
	while i + cnt[i] < n and a[cnt[i] + i] - a[i] <= 5:
		cnt[i] += 1
dp = [[0] * (k + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(k + 1):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if j + 1 <= k and i + cnt[i] <= n:
			dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i])
print(dp[n][k])


dp = []
for i in range(5005):
	dp.append([0] * 5005)
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
p = [0] * (n + 1)
for i in range(n):
	z = a[i] - 5
	for j in range(i + 1):
		if a[j] >= z:
			p[i] = j
			break
ans = -1
for i in range(1, n + 1):
	for j in range(k + 1):
		dp[i][j] = max(dp[i - 1][j], dp[p[i - 1]][j - 1] + (i - p[i - 1]))
		if j != k:
			ans = max(ans, dp[i][j])
print(ans)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
index = {}
for i in range(n):
	index[a[i]] = i
dp = [[1] * (k + 1) for i in range(n + 1)]
for i in range(n + 1):
	dp[i][0] = 0
for i in range(k + 1):
	dp[0][i] = 0
for i in range(1, n + 1):
	for item in range(5, -1, -1):
		if a[i - 1] + item in index:
			counter = index[a[i - 1] + item] - i + 1
			break
	for j in range(k + 1):
		if i > 0:
			dp[i][j] = max(dp[i - 1][j], dp[i][j])
		if j < k:
			dp[i + counter][j + 1] = max(dp[i + counter][j + 1], dp[i - 1][j] + counter + 1)
print(dp[n][k])


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
prev = [0 for i in range(n)]
for i in range(n):
	for j in range(i, -1, -1):
		if l[i] - l[j] <= 5:
			prev[i] = j
for i in range(k + 1):
	dp[0][i] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[prev[i - 1]][j - 1] + i - prev[i - 1])
print(dp[n][k])


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
l = [0 for i in range(n + 1)]
(i, li) = (n - 1, n - 1)
while i >= 0:
	while li >= 0 and a[i] - 5 <= a[li]:
		li -= 1
	l[i + 1] = li + 1
	i -= 1
dp[1][1] = 1
for i in range(2, n + 1):
	for j in range(1, k + 1):
		dp[i][j] = max(dp[i - 1][j], dp[l[i]][j - 1] + i - l[i])
print(max((dp[n][j] for j in range(1, k + 1))))


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	maxFromI = [0] * n
	end = -1
	for i in range(n):
		while end + 1 < n and a[end + 1] <= a[i] + 5:
			end += 1
		maxFromI[i] = end - i + 1
	dp = [[0] * (k + 1) for _ in range(n + 1)]
	for i in range(n):
		for j in range(k + 1):
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
			if j + 1 <= k:
				dp[i + maxFromI[i]][j + 1] = max(dp[i + maxFromI[i]][j + 1], dp[i][j] + maxFromI[i])
	print(dp[n][k])
main()


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	cnt = [0] * n
	for i in range(n):
		while i + cnt[i] < n and a[i + cnt[i]] - a[i] <= 5:
			cnt[i] += 1
	dp = [[0] * (k + 1) for _ in range(n + 1)]
	for i in range(n):
		for j in range(k + 1):
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
			if j + 1 <= k:
				dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i])
	print(dp[n][k])
main()


import heapq
arr = input()
(N, K) = [int(x) for x in arr.split(' ')]
arr = input()
arr = [int(x) for x in arr.split(' ')]
arr.sort()
data = [[0] * N for _ in range(K)]
left = 0
right = 0
res = 0
while left < N and right < N:
	if arr[right] > arr[left] + 5:
		left += 1
	else:
		data[0][right] = max(data[0][right - 1], right - left + 1)
		right += 1
for i in range(K):
	data[i][0] = 1
for j in range(1, K):
	left = 0
	right = 0
	res = 0
	while left < N and right < N:
		if arr[right] > arr[left] + 5:
			left += 1
		else:
			if left >= 1 and right >= 1:
				data[j][right] = max(data[j][right - 1], data[j][right], data[j - 1][left - 1] + right - left + 1)
			elif left == 0 and right >= 1:
				data[j][right] = max(data[j][right - 1], data[j][right], right - left + 1)
			right += 1
print(data[K - 1][N - 1])


from sys import stdin
input = stdin.readline
from collections import defaultdict

def f(a, n, k):
	cnt = [0] * n
	a = sorted(a)
	for i in range(n):
		while i + cnt[i] < n and a[i + cnt[i]] - a[i] <= 5:
			cnt[i] += 1
	dp = [[0] * (k + 1) for i in range(n + 1)]
	for i in range(n):
		for j in range(k + 1):
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
			if j + 1 <= k:
				dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i])
	return dp[n][k]
(n, k) = map(int, input().strip().split())
print(f([*map(int, input().strip().split())], n, k))


from collections import defaultdict

def solve(n, k, nums):
	nums.sort()
	new_nums = [0]
	for i in range(1, n):
		x = min(nums[i] - nums[i - 1], 6)
		new_nums.append(new_nums[-1] + x)
	cand_count = new_nums[-1] + 1
	candidates = [0] * cand_count
	for n in new_nums:
		for i in range(n - 5, n + 1):
			if 0 <= i < cand_count:
				candidates[i] += 1
	prev = [None] * cand_count
	max_val = 0
	for i in range(cand_count):
		max_val = max(max_val, candidates[i])
		prev[i] = max_val
	for ki in range(1, k):
		new = [None] * cand_count
		new[0:6] = prev[0:6]
		for i in range(6, cand_count):
			new[i] = max(new[i - 1], prev[i - 6] + candidates[i])
		prev = new
	print(prev[-1])

def solve_from_stdin():
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	solve(n, k, nums)

def test():
	(n, k) = (1000, 500)
	nums = list(range(n))
	solve(n, k, nums)
solve_from_stdin()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
dp = [[0 for i in range(k + 1)] for i in range(n + 1)]
(i, j) = (1, 2)
prev_max = [0 for i in range(k + 1)]
ans = 0
while i < n + 1:
	while j < n + 1 and a[j - 1] - a[i - 1] <= 5:
		j += 1
	for c in range(k):
		dp[j - 1][c + 1] = max(dp[j - 1][c + 1], prev_max[c] + (j - i))
		ans = max(ans, dp[j - 1][c + 1])
	for c in range(k):
		prev_max[c] = max(prev_max[c], dp[i][c])
	i = i + 1
print(ans)


kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, k) = kk()
ls = sorted(ll())
(vs, ne) = ([0] * n, [-1] * n)
b = 0
for a in range(n):
	while b < n and ls[b] - ls[a] < 6:
		b += 1
	(vs[a], ne[a]) = (b - a, b)
curr = [0] * (n + 1)
for _ in range(k):
	prev = curr
	curr = [0] * (n + 1)
	for i in range(n):
		curr[i] = vs[i] + prev[ne[i]]
	m = 0
	for i in range(n - 1, -1, -1):
		if m > curr[i]:
			curr[i] = m
		else:
			m = curr[i]
print(m)


import sys
import math
input = sys.stdin.readline
from functools import cmp_to_key

def pi():
	return int(input())

def pl():
	return int(input(), 16)

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

def ts():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
mod = 998244353
f = []

def fact(n, m):
	global f
	f = [1 for i in range(n + 1)]
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % m

def fast_mod_exp(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def inverseMod(n, m):
	return fast_mod_exp(n, m - 2, m)

def ncr(n, r, m):
	if r == 0:
		return 1
	return f[n] * inverseMod(f[n - r], m) % m * inverseMod(f[r], m) % m

def main():
	D()
dp = []

def D():
	[n, k] = ti()
	a = ti()
	a = sorted(a)
	cnt = [0 for i in range(n)]
	for i in range(n):
		c = 0
		for j in range(i, n):
			if a[j] - a[i] <= 5:
				c += 1
			else:
				break
		cnt[i] = c
	global dp
	dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
	ans = 0
	for i in range(n):
		for j in range(k + 1):
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
			if j + 1 <= k:
				dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i])
	print(dp[n][k])
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
from bisect import bisect_left, bisect_right
dp = [[0] * (k + 1) for i in range(n + 1)]
for (pos, good) in enumerate(a):
	for g_cnt in range(1, k + 1):
		group_size = pos + 1 - bisect_right(a, good - 6)
		dp[pos + 1][g_cnt] = max(dp[pos + 1 - group_size][g_cnt - 1] + group_size, dp[pos][g_cnt])
ans = max((dp[n][g_cnt] for g_cnt in range(k + 1)))
print(ans)


from sys import stdin, stdout

def read_input():
	global t
	t = int(input())

def solve():
	(n, k) = map(lambda x: int(x), input().split())
	arr = [0] + [int(x) for x in input().split()]
	arr.sort()
	dp = [[0 for x in range(k + 1)] for y in range(n + 1)]
	for j in range(1, k + 1):
		curr_team_size = 0
		worst_in_team = 1
		for i in range(1, n + 1):
			if arr[i] - arr[worst_in_team] <= 5:
				curr_team_size += 1
			else:
				curr_team_size += 1
				while arr[i] - arr[worst_in_team] > 5:
					curr_team_size -= 1
					worst_in_team += 1
			dp[i][j] = max(dp[i - curr_team_size][j - 1] + curr_team_size, dp[i - 1][j])
	print(dp[n][k])

def main():
	solve()
main()


(n, K) = map(int, input().split())
arr = sorted(map(int, input().split()))
freq = {}
for x in arr:
	freq[x] = freq.get(x, 0) + 1
arr = sorted(freq.keys())
freq = [freq[x] for x in arr]
n = len(arr)
dp = [[0 for _ in range(n + 1)] for _ in range(2)]
for k in range(1, K + 1):
	for i in range(n - 1, -1, -1):
		j = i
		curr = 0
		curr_ans = dp[k & 1][i + 1]
		while j < n and abs(arr[i] - arr[j]) <= 5:
			curr += freq[j]
			curr_ans = max(curr_ans, curr + dp[1 - (k & 1)][j + 1])
			j += 1
		dp[k & 1][i] = curr_ans
print(dp[K & 1][0])


from bisect import bisect_left, bisect_right
(n, k) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
for i in range(n):
	l = bisect_right(arr, arr[i] + 5)
	for j in range(k + 1):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if j < k:
			dp[l][j + 1] = max(dp[l][j + 1], dp[i][j] + l - i)
print(dp[n][k])


(n, k) = map(int, input().split())
dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
a = sorted([int(i) for i in input().split()])
cnt = [0 for i in range(n)]
for i in range(n):
	while i + cnt[i] < n and a[i + cnt[i]] - a[i] <= 5:
		cnt[i] += 1
for i in range(n):
	for j in range(k + 1):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if j + 1 <= k:
			dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i])
print(dp[n][k])


from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = set()
cnt = defaultdict(lambda : 0)
for i in a:
	cnt[i] += 1
	s.add(i)
s = list(s)
s.sort()
ok = []
(c, d) = ([], [])
for i in s:
	(c0, d0) = (0, 0)
	for j in range(6):
		c0 += cnt[i + j]
		d0 += min(cnt[i + j], 1)
	c.append(c0)
	d.append(d0)
m = len(s)
dp = [0] * (m + 1)
for _ in range(k):
	dp0 = [0] * (m + 1)
	for i in range(m):
		j = i + d[i]
		if j > m:
			break
		dp0[j] = max(dp0[j], dp[i] + c[i])
	ma = 0
	for i in range(m + 1):
		ma = max(ma, dp0[i])
		dp[i] = ma
	if dp[-1] == n:
		break
ans = dp[-1]
print(ans)


from bisect import bisect_right
import sys

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

def slv():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dp = [[0] * (k + 1) for i in range(n + 1)]
	ans = 0
	for ni in range(1, n + 1):
		v = a[ni - 1]
		cnt = bisect_right(a, v - 6)
		for gi in range(1, k + 1):
			dp[ni][gi] = dp[cnt][gi - 1] + (ni - cnt)
			dp[ni][gi] = max(dp[ni][gi], dp[ni][gi - 1], dp[ni - 1][gi])
	ans = max((dp[ni][k] for ni in range(1, n + 1)))
	print(ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
dp = [0] * n
start = a[0]
(k, i) = (0, 0)
while i < n:
	if a[i] - start > 5:
		dp[k] = i - k
		k += 1
		start = a[k]
	else:
		i += 1
dp[k] = n - k
for i in range(k + 1, n):
	dp[i] = dp[i - 1] - 1
if dp[0] == n:
	print(n)
	exit()
dp2 = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n - 1, -1, -1):
	for j in range(1, m + 1):
		dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j - 1] + 1, dp2[dp[i] + i][j - 1] + dp[i])
print(dp2[0][m])


(n, k) = map(int, input().split())
a = [int(X) for X in input().split()]
a.sort()
dp = [[0 for i in range(k + 1)] for j in range(n)]
dp[0][1] = 1
xx = 0
for i in range(1, n):
	while a[i] - a[xx] > 5:
		xx += 1
	for j in range(1, k + 1):
		dp[i][j] = dp[i - 1][j]
		if xx == 0:
			if j == 1:
				dp[i][j] = max(i - xx + 1, dp[i][j])
		else:
			dp[i][j] = max(dp[xx - 1][j - 1] + i - xx + 1, dp[i][j])
print(max(dp[n - 1]))


import sys
from collections import Counter

def i_ints():
	return map(int, sys.stdin.readline().split())
(n, k) = i_ints()
c = Counter(i_ints())
c2 = dict()
a = sorted(c)
for i in sorted(a):
	c2[i] = sum((c[j] for j in range(i, i + 6)))
len_a = len(a)
next_group = [-1] * len(a)
for i in range(len_a):
	for j in range(i + 1, len_a):
		if a[j] > a[i] + 5:
			next_group[i] = j
			break
maxes = [0] * n
for ii in range(k):
	old_maxes = maxes
	old_maxes.append(0)
	maxes = []
	for (i, aa) in enumerate(a):
		maxes.append(c2[a[i]] + old_maxes[next_group[i]])
	m = 0
	for i in range(len(a) - 1, -1, -1):
		if maxes[i] > m:
			m = maxes[i]
		else:
			maxes[i] = m
print(max(maxes))