World Conquest

Interview

Time limit2sMemory limit128 MB

Summary

Given population counts for N countries, find the maximum number of size-K groups where each group's members come from distinct countries.

Level: Medium5 of 10
Topics: Binary search, Greedy, Math
Solved: No attempts yet

Problem

Sejun has conquered N countries. He noticed that people from different countries are not close to one another, so he wants to form groups to help everyone become friendlier.

The groups must follow these rules.

Each group must contain exactly K people.
The people in one group must all come from different countries.

Given the number of people living in each country, find the maximum number of groups that can be formed. People who are not assigned to any group may be ignored.

For instance, if there are 5 countries with 4 people in each country and K is 4, at most 5 groups can be made. Each group can choose one person from 4 different countries among the 5 countries.

Input

The first line contains the number of countries N and the group size K. Both are positive integers, and they satisfy K <= N <= 50 and K <= 20.

The second line contains N integers separated by spaces, where each integer is the number of people living in one country. Each number is between 1 and 1,000,000,000, inclusive.

Output

Print the maximum number of groups that can be formed.

The answer is at most 2^63 - 1.

Examples4

Example 1
Input
```
5 4
4 4 4 4 4
```
Expected output
```
5
```
Example 2
Input
```
6 5
1 2 3 4 5 6
```
Expected output
```
3
```

Example 3

Input

6 2
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Expected output

3000000000

Example 4

Input

17 7
96 17 32 138 112 50 7 19 412 23 14 50 47 343 427 22 39

Expected output