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。