【2017.10.2】菌落合并

【题目描述】
小 M 培养了 n 个菌落。其中每个菌落有质量和颜色两种属性，颜色只可能为紫色或红色。小 M 想把所有的菌落合并成一个菌落。因为合并的过程非常费劲，小 M 每天只能进行一次合并，整个过程需要进行 n − 1 天。一次合并会将两个菌落变成一个菌落。如果原来两个菌落的颜色相同，两个菌落会进行融合，新的菌落质量为原来两个菌落质量之和，颜色不变；如果原来两个菌落的颜色不同，两个菌落会进行战斗，新的菌落质量为原来两个菌落质量之差，颜色为质量较大的那个菌落。需要特殊说明的是，中间过程中如果产生了质量为 0 的菌落，这个菌落也需要参与后续合并而不能直接舍弃；可以证明将质量为 0 的菌落视为紫色或红色都不影响后续的计算。
每天的合并结束后，小 M 都需要喂养当前的每个菌落。对于一个质量为 w 的菌落，小 M 需要花费 w^2 单位的能量对它进行一天的喂养。
小 M 希望你帮他求出菌落的最佳合并顺序，使得喂养所消耗的总能量最少。你只需要输出所需要的最小能量即可。

【输入格式】
从文件 germ.in 中读入数据。
输入的第一行包含一个正整数 T，表示数据的组数。对于所有的测试点，保证 T = 10。
对于每组数据，第一行包含一个正整数 n，表示最初菌落的个数。
接下来 n 行，每行包含一个正整数和一个字符串，表示这个菌落的质量和颜色。若字符串为 743481，表示这个菌落是紫色；若字符串为 8B0012，表示这个菌落是红色。保证不会出现其他的字符串，保证给出的正整数不超过 10 6 。

【输出格式】
输出到文件 germ.out 中。
对于每组数据，输出一行一个整数，表示消耗的最少总能量。注意这个值可能很大，请注意选用合适的数据类型来存储它

【样例输入】
10
4
3 743481
20 743481
7 8B0012
18 743481
3
10 8B0012
13 743481
13 8B0012
5
14 743481
16 8B0012
2 8B0012
9 8B0012
8 8B0012
4
11 8B0012
15 8B0012
4 8B0012
8 8B0012
2
11 8B0012
6 8B0012
4
8 8B0012
16 8B0012
16 8B0012
3 8B0012
2
20 743481
17 743481
3
6 8B0012
20 743481
13 8B0012
4
19 8B0012
15 743481
4 8B0012
1 743481
2
11 8B0012
14 8B0012

【样例输出】
2238
200
980
2688
289
3467
1369
86
107
625

【样例解释】
对于样例中的第一组数据，最优的合并方案如下：
1. 合并紫色的 20 和红色的 7，得到紫色的 13；喂养的能量花费为 3^2 +13^2 +18^2 = 502。
2. 合并紫色的 13 和紫色的 3，得到紫色的 16；喂养的能量花费为 16^2 +18^2 = 580。
3. 合并紫色的 16 和紫色的 18，得到紫色的 34；喂养的能量花费为 34^2 = 1156。
可以证明没有更优的方案。

【子任务】
n<=10。

同色的1~10就是个反例。