A. Inverse Pairs of Binary Strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a set of $$$n$$$ binary strings, each containing only the digits $$$\texttt{0}$$$ and $$$\texttt{1}$$$, you need to find an arrangement of these strings that minimizes the total number of inverse pairs in the final concatenated string. You may rearrange the strings in any order to achieve the minimum number of inverse pairs in the concatenated string.

Let's denote the $$$i$$$-th digit of the final concatenated string as $$$s_i$$$. An inverse pair is defined as a pair of indices $$$(i,j)$$$ such that $$$i \lt j$$$ and $$$s_i \gt s_j$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$), indicating the number of binary strings.

Each of the next $$$n$$$ lines contains a binary string. The sum of the lengths of all binary strings does not exceed $$$10^6$$$.

Output

Output a single integer representing the minimum number of inverse pairs.

Example
Input
3
1
11
101
Output
1
Note

For the sample, the final concatenated string with the minimum number of inverse pairs is $$$\texttt{101111}$$$.