幻影国建成了当今世界上最先进的高铁，该国高铁分为以下几类：

S—高速光子动力列车—时速1000km/h
G—高速动车—时速500km/h
D—动车组—时速300km/h
T—特快—时速200km/h
K—快速—时速150km/h

该国列车车次标号由上述字母开头，后面跟着一个正整数(<=1000)构成。

由于该国地形起伏不平，各地铁路的适宜运行速度不同。

因此该国的每一条行车路线都由K列车次构成。

例如：K=5的一条路线为：T120-D135-S1-G12-K856。

当某一条路线的末尾车次与另一条路线的开头车次相同时，这两条路线可以连接起来变为一条更长的行车路线。

显然若干条路线连接起来有可能构成一个环。

若有3条行车路线分别为:

x1-x2-x3
x3-x4
x4-x5-x1

x1~x5车次的速度分别为v1~v5

定义高铁环的值为(环上各条行车路线速度和)的平均值，即：

[(v1+v2+v3)+(v3+v4)+(v4+v5+v1)]/3.

所有高铁环的值的最大值称为最优高铁环的值。

给出M条行车路线，求最优高铁环的值。

输入格式

第一行为行车路线条数M。

接下来M行每行一条行车路线，由若干车次构成，各车次之间用’-‘号隔开，车次的标号方式如上所述。

数据保证输入的合法性。

输出格式

输出最优高铁环的值，四舍五入到最接近的整数。

若不存在这样的环，输出-1.

数据范围

$0 < M \le 50000$,
每条行车路线车次个数不超过20，数据保证结果不超过$2^{31}-1$。

输入样例：

3
T120-D135-S1
S1-G12
G12-K856-T120

输出样例：

1283

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解