Question
Maximize ‘xy’ Pairs
You are given an array of N strings, where each string is made up of only the characters ‘x’ and ‘y’. Now, consider a permutation of the first N natural numbers, denoted as {p1, p2, p3, …, pN}. Using this permutation, you create a new string T by concatenating the strings in the order of the permutation: T = t[p1] + t[p2] + t[p3] … t[pN], where t[i] is the ith string in the array.
Your task is to find the permutation that maximizes the “strength” of the resulting string T. The strength is defined as the number of times the subsequence “xy” appears in T. More formally, it is the number of pairs (i, j) such that i < j and T[i] = ‘x’ and T[j] = ‘y’.
Input
The first line contains a single integer N, the size of the array.
The next N lines contain the strings s[0], s[1], s[2],. s[N - 1].
Constraints:
1 ≤ N ≤ 105
It is guaranteed that the combined length of all strings doesn’t exceed 105.
The next N lines contain the strings s[0], s[1], s[2],. s[N - 1].
Constraints:
1 ≤ N ≤ 105
It is guaranteed that the combined length of all strings doesn’t exceed 105.
Output
Print the maximum Strength.
Example
Input
4
xxy
yx
x
yyyx
Output
18
Explanation
The given four strings can be concatenated as "x" + "xxy" + "yx" + "yyyx" = "xxxyyxyyyx".
There are total 18 "xy" pairs that can be formed using the above formed string, which is the maximum possible.
4
xxy
yx
x
yyyx
Output
18
Explanation
The given four strings can be concatenated as "x" + "xxy" + "yx" + "yyyx" = "xxxyyxyyyx".
There are total 18 "xy" pairs that can be formed using the above formed string, which is the maximum possible.