Maximum Complete Playlists

You are given a collection of songs. Each song is represented by a title and an artist. You need to form as many complete playlists as possible. A complete playlist consists of P songs selected from M available songs, with the requirement that each song in the playlist must be by a different artist.

More formally, suppose that you have M songs and each playlist requires exactly P songs. Let each song be represented as a tuple (title, artist). A playlist is valid if it contains P songs whose artists are all distinct. Your task is to compute the maximum number of complete playlists that can be made using the given songs. Note that each song can be used at most once.

You can express the main condition mathematically as finding the maximum integer K such that:

$$\sum_{i=1}^{n}\min(\text{count}_i, K) \ge K \times P, $$

where n is the number of distinct artists and count_i is the number of songs available from the i-th artist.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers M and P separated by a space, where M is the number of songs and P is the number of songs required for one playlist.
• The following M lines each contain two strings separated by a space: the song title and the artist name.

You may assume that the song titles and artist names do not contain whitespace.

outputFormat

Output a single integer: the maximum number of complete playlists that can be formed. The result should be written to standard output (stdout).

## sample

7 3
song1 artistA
song2 artistB
song3 artistC
song4 artistA
song5 artistB
song6 artistC
song7 artistD

2