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~ and pattern ~p_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_1~ times, and each pattern may be used no more than ~k_2~ times. What is the maximum number of collars you can use?

Input

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

The next ~n~ lines each contain two strings ~c_i~ and ~p_i~ (~1 \leq |c_i|, |p_i| \leq 10~), the color and pattern of the ~i~-th collar. Each color and pattern contains only lowercase English characters.

Output

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

Example

Input 1

10 3 2
green circle
green circle
green star
green triangle
red star
pink square
pink triangle
gray square
gray star
gray star

Output 1

8

The dogs can wear ~3~ green collars, ~2~ pink collars and ~3~ gray collars, so no color is used more than ~3~ times. At the same time, they wear ~2~ circle collars, ~2~ star collars, ~2~ square collars and ~2~ triangle collars, so no pattern is used more than ~2~ times.

Input 2

4 1 1
red circle
red square
blue circle
blue square

Output 2

2

Input 3

6 2 2
red square
red triangle
blue square
blue triangle
green square
green star

Output 3

5