给定 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

现在，请你从中挑选一些数，并将选出的数进行分组。

要求：

1. 选出的数最多划分为 kkk 组（至少 111 组）。
2. 同一组内，任意两数之差的绝对值不超过 555。
3. 所选出的数尽可能多。

请问，最多可以选出多少个数进行分组？

输入格式
第一行包含两个整数 nnn 和 kkk。

第二行包含 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

输出格式
输出一个整数，表示可以选出的最大整数数量。

数据范围
1≤k≤n≤5000,1≤k≤n≤5000,1≤k≤n≤5000,
1≤ai≤1091≤a_i≤10^91≤ai​≤109
输入样例1：

5 2
1 2 15 15 15

输出样例1：

5

输入样例2：

6 1
36 4 1 25 9 16

输出样例2：

2

输入样例3：

4 4
1 10 100 1000

输出样例3：

4

f[i][j]f[i][j]f[i][j] 表示在前 iii 个数中选，将其分为 jjj 组的方案
f[i][j]=max(f[i−1][j],f[k−1][j−1]+(i−k+1))f[i][j] = max(f[i-1][j], f[k-1][j-1] + (i - k + 1))f[i][j]=max(f[i−1][j],f[k−1][j−1]+(i−k+1))
f[i−1][j]f[i-1][j]f[i−1][j] 表示不选当前第 iii 个数，分为 jjj 组的方案
f[k−1][j−1]f[k-1][j-1]f[k−1][j−1] 表示选当前第 iii 个数，最右边的组的左边界取到第 kkk 个数的方案
kkk 满足 w[i]−w[k]<=5w[i]-w[k] <= 5w[i]−w[k]<=5 的最左边的数

#include
#includeusing namespace std;const int N = 5010;int n, m;
int w[N], f[N][N];int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &w[i]);sort(w + 1, w + n + 1);for(int i = 1, k = 1; i <= n; i++){while(w[i] - w[k] > 5) k++;for(int j = 1; j <= m; j++)f[i][j] = max(f[i-1][j], f[k-1][j-1] + (i - k + 1));}printf("%d\n", f[n][m]);return 0;
}