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
import java.util.*;
public class cfCheeseboard {

    static int f1(int n){
        if(n==1){
            return 1;
        }
        int x= (n%2==0) ? (n-1) : n;
        return f1(n-1)+x;
    }




    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int b=0,w=0;
        for(int i=0;i<n;i++){
            String s=sc.next();
            String im=sc.next();
            if(im.charAt(0)=='s'){
                w++;
            }
            if(im.charAt(0)=='h'){
                b++;
            }

        }
        int c= Math.max(w,b);
        int arr[]=new int[100];
        for(int i=1;i<n+1;i++) {
            int xx=f1(i);

            if(c<=xx){
                if(w==b &&( n%2==1 || n==2)){
                    System.out.println(i+1);
                    break;
                }
            System.out.println(i);
            break;
        }}
    }
}
