题目描述

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

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

该国列车车次标号由上述字母开头，后面跟着一个正整数（不超过 $1000$）构成。

由于该国地形起伏不平，各地铁路的适宜运行速度不同，因此该国的每一条行车路线都由 $K$ 个车次构成。

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

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

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

定义高铁环的值为环上各条行车路线速度和的平均值。

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

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

输入格式

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

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

数据保证输入的合法性。

输出格式

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

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

样例

输入样例：

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

输出样例：

1283

样例解释

三条路线分别是：

1. T120-D135-S1：速度为 $200 + 300 + 1000 = 1500$
2. S1-G12：速度为 $1000 + 500 = 1500$
3. G12-K856-T120：速度为 $500 + 150 + 200 = 850$

环为：路线1 → 路线2 → 路线3（可首尾相接成环）

环上速度和为 $1500 + 1500 + 850 = 3850$，平均值为 $3850 / 3 \approx 1283.33$，四舍五入为 $1283$。

数据范围

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

时空限制

• 时间限制：2 秒
• 空间限制：64 MB