After years of hard work and sacrifice, Angeloh was able to buy a house with a large garden. He always dreamed of a garden full of pigeons living happily in many small houses (with all the necessities and luxuries that a pigeon could want), forming a mini city.
At the local breeding ground, they told him that there are $$$n$$$ different species, and they have $$$p_i$$$ pigeons of the $$$i$$$-th species available to sell to him.
Studies show that pigeons are happier if they live in houses inhabited by exactly $$$k$$$ pigeons. Angeloh wants his pigeons to be optimally happy, and he also loves to see the various colors of all the species; for this reason, he wants to buy pigeons in such a way that he can assign each one to a house and each house houses exactly $$$k$$$ pigeons of different species.
Angeloh is not sure how many or which pigeons to buy to realize his vision; but, more importantly, he needs to start building the houses so that his pigeons are safe and sound. That's why he asks for your help. For now, Angeloh doesn't need to know which pigeons to buy, but he wants you to tell him the maximum number of houses he can build, so that it is possible to buy and assign pigeons to each house following his specifications and that no house remains empty.
The first line will contain two integers $$$n$$$ and $$$k$$$ (1 $$$\leq n, k \leq 10^5$$$), indicating the number of pigeon species in the breeding ground and the number of pigeons that must live in the same house to be optimally happy.
The next line contains $$$n$$$ integers $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$), indicating the number of pigeons of the $$$i$$$-th species available for purchase.
A single integer must be printed, indicating the maximum number of houses that Angeloh can build following Angeloh's specifications.
3 2 3 4 1
4
2 3 5 4
0
5 3 5 20 7 2 13
13
For the first example case, it is possible to have pigeons of the first and second species in 3 houses, and pigeons of the second and third species in 1 house. Note that it is impossible to build more houses without leaving any empty because Angeloh would buy all the available pigeons at the breeding ground.
For the second example case, it is impossible for there to be a house with 3 different species of pigeons.
