题目描述

​ 今天的Kiana是一名糕点师，她的任务是制作出最美味的奶油蛋糕塔。
​ Kiana一共有\(n\)块蛋糕用于制作蛋糕塔，其中第\(i\)块蛋糕的美味度为\(D_i(1 \le D_i \le 1000)\)。每块蛋糕的顶面和底面都各涂有一种奶油，奶油总共有四种不同的类型，分别用字母'X'、'Y'、'Z'和'W'来表示。由于不同种类的奶油混在一起会变得难以下咽，因此Kiana规定，一块蛋糕能够放在另一块蛋糕上面，当且仅当前者底面的奶油和后者顶面的奶油是同一种类的。
​ 为了制作尽可能美味的蛋糕，Kiana允许对每块蛋糕进行翻转，即可以任意交换某些蛋糕的顶面和底面，且最后制作出来的蛋糕塔最下面一块蛋糕的底面和最上面一块蛋糕的顶面的奶油种类是无所谓的。
​ 制作好的蛋糕塔的美味度为使用的蛋糕的美味度之和，因为有奶油种类的限制，所以不一定\(n\)块蛋糕都能被用来制作蛋糕塔。现在Kiana想知道，自己能做出的美味度最大的奶油蛋糕塔美味度是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式
第一行包含一个正整数\(n\)，表示Kiana可以选用的蛋糕数量。
接下来\(n\)行，第\(i\)行包含一个正整数\(D_i\)与两个字符\(T_i\)和\(B_i\)，分别表示第\(i\)块蛋糕的美味度和其顶面与底面的奶油种类。
输出格式
输出共一行，包含一个正整数，表示美味度最大的奶油蛋糕塔的美味度。

输入输出样例

输入样例#1：

5
1 W X
2 X Y
3 Y Z
4 X Z
5 W Z

输出样例#1：

15

输入样例#2：

cake2.in

输出样例#2：

cake2.out

样例解释

​ Kiana一共有\(5\)块蛋糕可以用于制作蛋糕塔，其美味度和奶油情况如下：
​ 第\(1\)块：美味度为\(1\)，顶面是奶油W，底面是奶油X
​ 第\(2\)块：美味度为\(2\)，顶面是奶油X，底面是奶油Y
​ 第\(3\)块：美味度为\(3\)，顶面是奶油Y，底面是奶油Z
​ 第\(4\)块：美味度为\(4\)，顶面是奶油X，底面是奶油Z
​ 第\(5\)块：美味度为\(5\)，顶面是奶油W，底面是奶油Z
​ Kiana可以采取如下策略制作蛋糕塔：将第\(3\)块蛋糕放在最下面，第\(2\)块蛋糕放在第\(3\)块蛋糕上面，第\(4\)块蛋糕翻转后放在第\(2\)块蛋糕上面，第\(5\)块蛋糕放在第\(4\)块蛋糕上面，最后把第\(1\)块蛋糕翻转后放在第\(5\)块蛋糕上面，这样所有的蛋糕都被用于制作蛋糕塔，故总美味度最大为\(15\)。

数据范围

对于\(25\%\)的数据，保证\(1\leq n\leq 10\)。
对于\(25\%\)的数据，保证\(1\leq n\leq 500\)。
对于\(25\%\)的数据，保证\(1\leq n\leq 5000\)。
对于\(25\%\)的数据，保证\(1\leq n\leq 5\times 10^5\)。
上面每一档数据中，各有一组数据保证只有三种不同的奶油，还有两组数据保证所有蛋糕美味度相同。