Every dog has its day. While touring the Serengeti, you came across a particularly friendly pack of African wild dogs. As an endangered species, they're worth protecting, so you'd like to fit them with collars to track the pack into the future. There are plenty of dogs, but you have only ~n~ collars to hand out, the ~i~-th of which has color ~c_i~.

Your task is to choose which collars will be assigned to the dogs. To keep things interesting, each color may be used no more than ~k~ times. What is the maximum number of collars you can use?

Input

The first line contains two integers ~n~ and ~k~ (~1 \leq n, k \leq 10^5~), the number of collars you have at your disposal, and the maximum number of times you can use a single color.

The next ~n~ lines contain a string ~c_i~ (~1 \leq |c_i| \leq 10~), the color of the ~i~-th collar. Each color contains only lowercase English characters.

Output

Output the maximum number of collars you can assign to the dogs.

Example

Input 1

11 3
red
red
red
red
red
blue
blue
blue
blue
orange
purple

Output 1

8

The dogs can wear ~3~ red collars, ~3~ blue collars, ~1~ orange collar and ~1~ purple collar. No color is used more than ~3~ times.

Input 2

4 1
red
red
red
blue

Output 2

2

Input 3

4 3
red
red
red
blue

Output 3

4