B. Responsible Laundry
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One of the features of adult life is the proper approach to washing clothes:

  • if you wash a new colored sweater together with white socks — the socks will no longer be quite white;
  • if you wash very dirty trousers together with several T-shirts — then you will have to wash the T-shirts again separately afterward.

Many examples can be invented, but here we will fix several basic rules of a "responsible washer":

  • all socks can be washed together, but separately from all other clothes;
  • for the remaining clothes, the following rule applies:
    • bright clothes — only with the same color;
    • white clothes separately;
    • dark, but not bright, clothes separately;
  • T-shirts can only be washed with T-shirts;
  • an additional rule for sweaters and trousers:
    • they can be washed together with each other;
    • but no more than 2 sweaters and/or trousers in one wash, otherwise they will not be washed properly.

Your wardrobe contains $$$N$$$ clothing items, each described by its color and type.

Determine the minimum number of washes required according to the rules described above.

Input

The first line contains one integer $$$N$$$ $$$(1 \le N \le 10^4)$$$ — the number of clothing items available.

Each of the next $$$N$$$ lines contains the description of one clothing item in the wardrobe: two words separated by a space $$$c_i$$$ $$$t_i$$$ — the color and the type of the clothing item, respectively.

$$$c_i$$$ can be one of the following words:

  • White — white (light color);
  • Black — black (dark color);
  • Yellow — yellow (bright and light color);
  • Red — red (bright and light color);
  • Green — green (bright and dark color);
  • Blue — blue (dark color);
  • Gray — gray (dark color).

$$$t_i$$$ can be one of the following words:

  • Socks — a pair of socks;
  • T-shirt — T-shirt;
  • Hoodie — sweater;
  • Trousers — trousers;
  • Jeans — jeans (also trousers).
Output

Print one integer — the minimum number of washes taking into account all the rules described above.

Examples
Input
10
Red Socks
Black Jeans
White T-shirt
Yellow T-shirt
Red Hoodie
Green Socks
Blue T-shirt
White T-shirt
Blue Hoodie
Gray Trousers
Output
7
Input
8
Yellow T-shirt
Black T-shirt
Red T-shirt
Gray T-shirt
Red T-shirt
Blue T-shirt
Green T-shirt
Blue T-shirt
Output
4
Input
6
Red Socks
Black Socks
Black Socks
White Socks
Blue Socks
White Socks
Output
1
Input
9
Blue Hoodie
Black Jeans
White Trousers
Green Hoodie
Red Hoodie
Blue Jeans
Blue Jeans
White Jeans
White Hoodie
Output
6
Note

Example 1.

  • Both red and green socks can be washed together — one wash for all socks.
  • Two white T-shirts are washed separately from the other T-shirts.
  • The yellow (bright) T-shirt is washed separately.
  • The red (bright) sweater is washed separately.
  • The blue (dark) T-shirt is washed separately from dark sweaters and trousers.
  • The blue sweater, gray trousers, and black jeans can be washed together, but no more than two such items in one wash, so two washes are needed.

In total, there are $$$7$$$ washes: $$$1$$$ for socks, $$$3$$$ for T-shirts, $$$1$$$ for the bright sweater, and $$$2$$$ for the dark sweaters and trousers.

Example 2.

  • Yellow, red, and green T-shirts — three separate washes for three separate bright colors.
  • Black, blue, and gray T-shirts are washed separately (all dark T-shirts together).

In total, there are $$$4$$$ washes: one each for red, yellow, green, and dark T-shirts, regardless of the number of items of each color.

Example 3.

All socks are washed in one wash, regardless of their number and color.

Example 4.

  • White items are washed separately (two washes for three items, since there can be no more than two sweaters and/or trousers in one wash).
  • The green and red sweater are washed separately (two washes, one for each color).
  • Gray, blue, and black trousers and hoodies are washed separately from white and bright items (two washes for four items).

In total, there are $$$6$$$ washes.