Problem2113--桶排序-选卡片

2113: 桶排序-选卡片

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 62  Solved: 36
[Status] [Submit] [Creator:]

Description

有 n 张卡片(1 ≤ n ≤ 100,000),每张卡片都有一个号码,号码是一个 1 到 m 范围内(包括 1 和 m)的整数(1 ≤ m ≤ 1000)。可能存在多张卡片号码相同。

你需要从 n 张卡片中选择尽可能多的卡片,同时满足选择的这些卡片中不同的号码数量不超过 k。

求:能够选择的卡片的最大数量。

Input

第一行,三个整数 n、m、k(1 ≤ n ≤ 100,000, 1 ≤ k ≤ m ≤ 1000),分别表示卡片数量、卡片号码的范围以及选择的卡片的不同号码的最大数量。  

第二行,n 个整数,两两之间以一个空格分隔,表示每张卡片的号码(均为 1 到 m 范围内的整数)。

Output

输出一个整数,表示在选择的卡片的不同号码数不超过 k 的情况下,能够选择的卡片的最大数量。

Sample Input Copy

【样例输入1】
5 5 2
1 2 2 3 4
【样例输出1】
3
【样例输入2】
5 5 2
2 2 3 2 3
【样例输出2】
5
【样例输入3】
11 100 2
2 3 3 66 66 66 66 66 3 5 5
【样例输出3】
8

HINT

【样例解释】
样例1:选择2张号码为2的卡片,然后再从其它3张卡片中任选一张,最多能选择3张卡片;
样例2:所有的卡片都选择;
样例3:选择号码为66和3的卡片,对应的卡片数量为 5+3=8。

Source/Category