[[原文:http://acm.pku.edu.cn/JudgeOnline/problem?id=2246]]
----
''時間制限'':1000ミリ秒
''メモリ制限'':65536KB
&br;

連鎖行列積

*問題 [#l315f216]
A,B,C,D,Eを行列としたとき、A*B*C*D*Eという式を評価してみよう。
行列同士の積は連結性があるため、掛け算を行う順番は任意にできる。しかし、必要になる初等的な掛け算の数は、選んだ順番に強く影響される。
例えば、Aを50×10、Bを10×20、Cを20×5の行列とする。
ここで、A*B*Cを計算する方法は、(A*B)*CとA*(B*C)とがある。前者は15000回の初等的な掛け算が必要だが、後者は3500回しか必要としない。

行列の積の計算の仕方が与えられたとき、必要となる初等的な掛け算の数を求めるプログラムを作成しなさい。

*入力 [#fe2fb646]

入力は、行列のリストと式のリストの2つの部分からなる。
1行目には、1つ目の部分にある行列の数を表す1つの整数 n (2<=n<=26)が書かれている。続くn行は、各行にその行列の名前を表す英字大文字1文字と、列と行の数を表す2つの整数がある。
2つ目の部分は、次のような構文に厳密に従っている。(EBNF記法で与えられる)

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

*出力 [#uebae011]

2つ目の部分にある各式について、行列の積が定義されないときは"error"と、そうでない時は、式を評価するときに丸括弧のところで必要となる初等的な掛け算の回数の合計を表す数を1行で出力しなさい。

*入力例 [#t7af6dbf]

 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))

*出力例 [#j54c5d6b]

 0
 0
 0
 error
 10000
 error
 3500
 15000
 40500
 47500
 15125

*出典 [#gf9a8522]

Ulm Local 1996