Question
Maximize Power (QOTD)
You are given an array of N strings which consists of only two characters ‘x’ and ‘y’. Consider a permutation {p1, p2, p3……. pN} of first N natural numbers and we make a string S = s[p1]+s[p2, ]+s[p3]…. s[pN] where s[i] represents the ith 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.
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 <= 1055
It is guaranteed that the combined length of all strings doesn’t exceed 105.
The next N lines contain the strings s[1], s[2],. s[N].
Constraints:
1 <= N <= 1055
It is guaranteed that the combined length of all strings doesn’t exceed 105.
Output
Print the maximum Power.
Example
Sample Input:
4
xxy
yx
x
yyyx
Sample Output:
18
4
xxy
yx
x
yyyx
Sample Output:
18