Пес Пушок уже который час гоняется за Импом по всему дому.
По счастью, Имп хорошо осведомлен о главном страхе Пушка — жутком роботе-пылесосе.
При передвижении по дому робот-пылесос генерирует строку t из букв «s» and «h», производящую много шума. Определим шум строки t как количество вхождений строки «sh» в нее как подпоследовательность, иными словами, количество таких пар (i, j), что i < j и 
и 
.
В данный момент робот неактивен. Имп знает, что в памяти робота лежит набор строк ti, которые можно переставлять произвольным образом. При запуске эти строки склеиваются в выбранном порядке и получается строка t; итоговый шум получается равным шуму этой склейки.
Помогите Импу найти максимальное значение шума, которое он может получить, переставляя строки произвольным образом.