Question

Maximize Power (QOTD)

You are given an array of N strings which consists of only two characters ‘x’ and ‘y’. Consider a permutation {p

The power of a string is defined as the number of occurrences of subsequence ‘xy’ in it, or more formally, it is the number of pairs(i, j) such that i

You have to find this maximum Power.

_{1}, p_{2}, p_{3}……. p_{N}} of first N natural numbers and we make a string**S = s[p**where s[i] represents the i_{1}]+s[p_{2}, ]+s[p3]…. s[p_{N}]^{th}string in the given array. Select such a permutation that the resulting string S has maximum power.The power of a string is defined as the number of occurrences of subsequence ‘xy’ in it, or more formally, it is the number of pairs(i, j) such that i

You have to find this maximum Power.

Input

The first line contains a single integer N, the size of the array.

The next N lines contain the strings s[1], s[2],. s[N].

Constraints:

1 <= N <= 10

It is guaranteed that the combined length of all strings doesn’t exceed 10

The next N lines contain the strings s[1], s[2],. s[N].

Constraints:

1 <= N <= 10

^{5}5It is guaranteed that the combined length of all strings doesn’t exceed 10

^{5}.Output

Print the maximum Power.

Example

Sample Input:

4

xxy

yx

x

yyyx

Sample Output:

18

4

xxy

yx

x

yyyx

Sample Output:

18