问题描述

小核桃一行人被困在了 时空隧道 之内，现在他们在尝试破解密码。

小核桃知道密码的提示：一个由 $0$ 和 $1$ 字符组成的字符串，密码就是这个字符串的逆序对数。

但是由于故障，这个提示破碎了，变成了 $n$ 个由 $0$ 和 $1$ 组成的字符串，现在他们需要把这 $n$ 个字符串自由排列并拼接起来得到原提示和密码。

当然，可能的拼接方案太多了，不过幸运的是，得到了某位的帮助，他们知道提示的逆序对数是所有拼接方案里逆序对数最少的。

但即使这样，这个问题也很难，所以他们希望你能够帮助他们，得到最后的密码。

令 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符，一个逆序对是指一个点对 $(i,j)$ 满足 $i<j$ 且 $s_i>s_j$。

输入描述

第一行一个正整数 $n$ ，表示字符串的个数。

接下来 $n$ 行每行一个给定的字符串。

输出描述

输出一个整数表示密码，即最少的逆序对数。

3
1
11
101

1

3
1010
111
101

6

样例解释 1

逆序对数最少的字符串为 101111.

数据范围和说明

设 $M$ 为所有字符串长度之和。

大样例

大样例下载