题目描述

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

$\red {S}$—高速光子动力列车—时速$\red {1000km/h}$

$\red {G}$—高速动车—时速$\red {500km/h}$

$\red {D}$—动车组—时速$\red {300km/h}$

$\red {T}$—特快—时速$\red {200km/h}$

$\red {K}$—快速—时速$\red {150km/h}$

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

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

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

例如：$\red {K=5}$的一条路线为：$\red {T120-D135-S1-G12-K856}$。

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

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

若有$\red {3}$条行车路线分别为:

$\red {x_1-x_2-x_3}$

$\red {x_3-x_4}$

$\red {x_4-x_5-x_1}$

$\red {x_1\sim x_5}$车次的速度分别为$\red {v_1\sim v_5}$

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

$\red {[(v_1+v_2+v_3)+(v_3+v_4)+(v_4+v_5+v_1)]/3}$.

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

给出$\red {M}$条行车路线，求最优高铁环的值。

输入格式

第一行为行车路线条数$\red {M}$。

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

数据保证输入的合法性。

输出格式

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

若不存在这样的环，输出$\red {-1}$.

样例

输入样例

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

输出样例

1283

提示

$\red {0<M≤50000}$,

每条行车路线车次个数不超过$\red {20}$，数据保证结果不超过$\red {2 ^{31}−1}$。