952_E. Cheese Board
Not to be confused with [chessboard](https://en.wikipedia.org/wiki/Chessboard).

<image>

Input

The first line of input contains a single integer N (1 ≤ N ≤ 100) — the number of cheeses you have.

The next N lines describe the cheeses you have. Each line contains two space-separated strings: the name of the cheese and its type. The name is a string of lowercase English letters between 1 and 10 characters long. The type is either "soft" or "hard. All cheese names are distinct.

Output

Output a single number.

Examples

Input

9
brie soft
camembert soft
feta soft
goat soft
muenster soft
asiago hard
cheddar hard
gouda hard
swiss hard


Output

3


Input

6
parmesan hard
emmental hard
edam hard
colby hard
gruyere hard
asiago hard


Output

4
```python
a, b = 0, 0
n = int(input())
for i in range(n):
    x, y = input().split()
    if y == 'soft':
        a += 1
    else:
        b += 1

for i in range(1, 1000):
    n = i*i
    y = n // 2
    x = n - y
    if (a <= x and b <= y) or (a <= y and b <= x):
        print(i)
        break
```