Robot Vacuum Cleaner

개 Pushok은 이미 몇 시간째 Imp를 쫓고 있다.

다행히 Imp는 Pushok이 로봇 청소기를 무서워한다는 것을 알고 있다.

로봇은 움직이는 동안 문자 's'와 'h'로 이루어진 문자열 t를 생성하며, 이는 많은 소음을 낸다. 문자열 t의 소음을 그 안에서 문자열 "sh"이 부분 수열로 등장하는 횟수, 다시 말해 i < j이고 이며 인 순서쌍 (i, j)의 개수로 정의한다.

현재 로봇은 꺼져 있다. Imp는 로봇의 메모리에 문자열 ti의 수열이 있으며, 그 순서를 자유롭게 바꿀 수 있다는 것을 알고 있다. 로봇을 작동시키면 주어진 순서대로 이 문자열들을 이어 붙인 문자열 t를 생성한다. 결과 문자열의 소음은 이렇게 이어 붙인 문자열의 소음과 같다.

Help Imp 문자열의 순서를 바꾸어 얻을 수 있는 최대 소음을 구한다.

첫째 줄에 로봇의 메모리에 있는 문자열의 개수를 나타내는 하나의 정수 n (1 ≤ n ≤ 105)이 주어진다.

다음 n개의 줄에 문자열 t1, t2, ..., tn이 한 줄에 하나씩 주어진다. 문자열은 비어 있지 않고 영문자 's'와 'h'만 포함하며, 문자열의 총길이는 105를 초과하지 않는다.

Imp가 문자열의 순서를 바꾸어 얻을 수 있는 가능한 최대 소음을 나타내는 하나의 정수를 출력한다.

첫 번째 예제에서 최적의 연결 결과는 ssshhshhhs이다.