← 返回题目列表

Codeforces · 922/D

D. 机器人吸尘器

中文机器翻译题面 查看原题

Pushok 狗已经追赶 Imp 几个小时了。

幸运的是,Imp 知道 Pushok 害怕机器人吸尘器。

机器人在移动时会生成由字母“s”和“h”组成的字符串 t,从而产生大量噪音。我们将字符串 t 的噪声定义为字符串“sh”作为其中的子序列出现的次数,换句话说,就是这样的对 (i, j) 的数量,即 i < j 且 $$t_{i} = s$$ 且 $$t_j = h$$。

机器人目前已关闭。 Imp知道它的内存中有一个字符串序列ti,并且他可以任意改变它们的顺序。当机器人启动时,它会生成字符串 t 作为这些字符串按给定顺序的串联。生成的字符串的噪声等于该串联的噪声。

帮助 Imp 找到通过改变弦乐顺序可以达到的最大噪音。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 机器人内存中的字符串数量。

接下来的 n 行包含字符串 t1, t2, ..., tn,每行一个。保证字符串非空,仅包含英文字母's'和'h'且总长度不超过105。

输出

打印一个整数——通过改变字符串的顺序,Imp 可以达到的最大可能噪声。

示例

输入 #1

4
ssh
hs
s
hhhs

输出 #1

18

输入 #2

2
h
s

输出 #2

1

注意

第一个样本中的最佳串联是 ssshhshhhs。