Identical Pizzas

We present our protagonist, Takis, a young Greek man whose dream since childhood has been to open his own pizzeria. Today, he is very close to making this dream a reality.

To save as much money as possible, Takis's plan is not to hire any staff, but to make and serve the pizzas himself. In his warehouse, he has ~N~ ingredients. The quantities of the various ingredients are denoted by the positive integers ~a_1~, ~a_2~, ~...~, ~a_N~. Takis's goal is to make as many identical pizzas as possible.

We say that some pizzas are identical when they all:

• consist of the same ingredients, and
• contain the same (positive integer) quantity of each of these ingredients.

To make his pizzas less "boring", Takis has imposed one more restriction: each pizza must contain at least ~K~ different ingredients. Determine the maximum number of identical pizzas Takis can make while satisfying this restriction.

Problem

Write a program in one of the languages supported by the Greek Olympiad in Informatics (PASCAL, C, C++, JAVA) that reads the input data from samepizzas.in and writes the results to samepizzas.out.

Input Files (samepizzas.in)

The first line contains the subtask number (see below).

The second line contains two integers ~N~ and ~K~, separated by a space: the number of ingredients Takis has and the minimum number of different ingredients each pizza must contain.

The third line contains ~N~ integers ~a_1~, ~a_2~, ~...~, ~a_N~, separated by spaces: the quantities of the ingredients.

Output Files (samepizzas.out)

The output must contain a single line with an integer: the maximum number of identical pizzas Takis can make while satisfying the above restriction.

Sample Input and Output Files

Input:

4
5 3
12 6 7 6 4

Output:

6

Explanation:

Takis can make ~6~ identical pizzas, each containing two units of the first ingredient, one unit of the second ingredient, and one unit of the fourth ingredient. He can also choose other combinations of ingredients that yield ~6~ identical pizzas, but there is no way for him to make more.

Constraints

• ~1 \le K \le N \le 200.000~
• ~1 \le a_i \le 1.000.000.000~

Subtasks

1. (10 points) ~N = 2~
2. (15 points) ~K = N~
3. (25 points) ~K = 1~
4. (10 points) ~N \le 10.000~
5. (40 points) There are no further restrictions.

Notes

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~1~ sec.
• Maximum available memory: ~64~ MB.
• Source code headers: At the beginning of your source code, you must use the following headers.

(* USER: username
LANG: PASCAL
TASK: samepizzas *)

for PASCAL code

/* USER: username
LANG: C
TASK: samepizzas */

for C code

/* USER: username
LANG: C++
TASK: samepizzas */

for C++ code

/* USER: username
LANG: Java
TASK: samepizzas */

for Java code

Warning: The answer may exceed ~2^{32}~. Also, make sure to read the input and print the output efficiently, especially if you are using C++ or Java.