Codeforces E. K Balanced Teams(1133E)

E. K Balanced Teams

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are a coach at your local university. There are nn students under your supervision, the programming skill of the ii-th student is aiai.

You have to form kk 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 kk (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 55. 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 kk (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 nn and kk (1≤k≤n≤50001≤k≤n≤5000) — the number of students and the maximum number of teams, correspondingly.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is a programming skill of the ii-th student.

Output

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

Examples

input

Copy

5 2 1 2 15 15 15

output

Copy

5

input

Copy

6 1 36 4 1 25 9 16

output

Copy

2

input

Copy

4 4 1 10 100 1000

output

Copy

4

============================================

可以将数组排序，把题目转化为将数组分为不想交的k组，使其值最大。和经典的子数组和最大的dp题不同，这里加了数组中大小最大和最小值不能超过5的限制。dp思路就是在求i个分组是以第j个结尾的数时，结尾j有选或不选2种情况，如果选择的话，可以贪心的选，以j结尾的子数组往前包含尽能多的值。这里可以先预处理一下，求每个j和满足<=j前面最远的值，或者求dp的时候可以利用双指针。

import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int k=sc.nextInt(); int[] A=new int[n]; for(int i=0;i<n;i++)A[i]=sc.nextInt(); Arrays.sort(A); int[] dp=new int[n]; for(int i=0;i<k;i++){ int[] ndp=new int[n]; for(int j=0,r=0;r<n;){ while(r<n&&A[j]+5>=A[r]){//以r为结尾 尽可能取得多 ndp[r]=Math.max(r==0?0:ndp[r-1],r-j+1+(j==0?0:dp[j-1])); r++; } while(r<n&&A[j]+5<A[r]){ j++; } if(r<n) { ndp[r]=Math.max(r==0?0:ndp[r-1],r-j+1+(j==0?0:dp[j-1])); } } dp=ndp; } System.out.println(dp[n-1]); } }