1504_矩阵连乘

Alice现在有1岁8个月了，整天跑跑跳跳，上串下跳，除了喜欢玩滑梯、骑木马，就是爱数学。其中一个重要的原因就是做完数学题之后，爸爸都会奖励东西给她吃。（好像马戏团训练动物就是这样子的…）现在她要计算形如A×B×C×D×E这样的表达式，其中A, B, C, D和E都是矩阵。

几个矩阵连乘是可以采用结合律的，乘法执行的先后次序是可以任意设定的。然而，所需执行的基本乘法次数，强烈依赖于Alice所选择的矩阵相乘的优先顺序。

例如，A是一个50×10的矩阵，B是一个10×20的矩阵，C是一个20×5的矩阵。

计算A×B×C就有两种不同的策略，一种是(A×B)×C，另一种是A×(B×C)。第一种策略一共需要执行15000次基本乘法，第二种策略则只需3500次。

Alice请你帮忙写一个程序，计算一个给定的矩阵运算策略所需执行的基本乘法次数。

输入部分由2部分组成：第一部分是矩阵清单，第二部分是表达式清单。

输入的第一行是单独一个整数n（1 ≤ n ≤ 26），表示矩阵的个数。接下来有n行，每行的前面一个大写字母，表示矩阵的名字，接着2个整数，表示该矩阵的行数和列数。这就是第一部分，矩阵清单。

输入的第二部分严格遵守以下语法规则（以EBNF形式给出）

SecondPart = Line { Line }
Line       = Expression
Expression = Matrix | "(" Expression Expression ")"
Matrix     = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

对第二部分的每一条表达式，如果表达式里的前后矩阵不相容（如样例中的的A×A是不可执行的，因为50×10的矩阵不可与50×10的矩阵相乘），不可做乘法时，输出一行"error"。否则，输出这些矩阵根据所给括号的优先次序执行乘法所需的基本乘法次数。

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

0
0
0
error
10000
error
3500
15000
40500
47500
15125