| Codeforces Round 461 (Div. 2) |
|---|
| Закончено |
Пес Пушок уже который час гоняется за Импом по всему дому.
По счастью, Имп хорошо осведомлен о главном страхе Пушка — жутком роботе-пылесосе.
При передвижении по дому робот-пылесос генерирует строку t из букв «s» and «h», производящую много шума. Определим шум строки t как количество вхождений строки «sh» в нее как подпоследовательность, иными словами, количество таких пар (i, j), что i < j и 
и 
.
В данный момент робот неактивен. Имп знает, что в памяти робота лежит набор строк ti, которые можно переставлять произвольным образом. При запуске эти строки склеиваются в выбранном порядке и получается строка t; итоговый шум получается равным шуму этой склейки.
Помогите Импу найти максимальное значение шума, которое он может получить, переставляя строки произвольным образом.
В первой строке задано число n (1 ≤ n ≤ 105) — количество строк в памяти робота-пылесоса.
В следующих n строках заданы сами строки t1, t2, ..., tn, по одной в строке. Гарантируется, что они непусты, состоят только из букв латинского алфавита «s» и «h», а суммарная длина набора строк не превосходит 105.
Выведите одно число — максимальный уровень шума, который можно достичь оптимальным переупорядочиванием набора строк.
4
ssh
hs
s
hhhs
18
2
h
s
1
В первом примере оптимальной склейкой является ssshhshhhs.
