1726 - 作品展示
描述

稠州中学共有 n 个美术小组,其中第 i 个小组中有学生 x_i名。

恰逢学校英语节,英语节内有一项跨小组标志设计作品展示活动,每件作品需要由至少 m 个不同小组的成员合作完成,且每个学生只能参与一个作品。

请问,按给定小组数量及每个小组的人数,最多能完成多少件作品?


输入

输入共两行:

第一行,两个正整数 n,m

第二行,n个正整数x1,x2,x3......xn


输出

输出一个整数,表示答案


样例

输入

4 3
1 5 1 5

输出

2
提示
  • 对于 30%30% 的数据,1≤�,�≤101n,m10

  • 对于 60%60% 的数据,1≤�,�≤10001n,m1000

对于 100% 的数据,1≤n,m≤100,000,1\leq x_i \leq 10^9

样例说明:

假设 A小组1人,B小组5人,C小组1人,D小组5人;

A小组1人+B小组1人+D小组1人,满足成员起码来自3个不同小组

B小组1人+C小组1人+D小组1人,满足成员起码来自3个不同小组

但之后只剩B,D小组有人多余,无法再组成作品小组;

因此,最多只能组成2个小组,完成2个作品


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 51
通过次数 13