describe
The computation of matrix multiplication is strongly related to the order of matrix multiplication .
for example ：
A It's a 50×10 Matrix ,B yes 10×20 Matrix ,C yes 20×5 Matrix
Calculation ABC There are two orders ：（（AB）C） perhaps （A（BC））, The former needs to calculate 15000 Times multiplication , The latter only needs 3500 Time .
Write a program to calculate the multiplication times required for different calculation sequences .
This question contains several groups of sample input ！
Input description ：
Input multiple lines , First enter the number of matrices to calculate the multiplication n, The number of rows per matrix , Number of columns , in total 2n Number of numbers , Finally, enter the rule to calculate
The calculation rule is a string , It consists only of left and right parentheses and capital letters （'A'~'Z'） form , Make sure the parentheses match and the input is legal ！
Output description ：
Output the number of multiplications to be performed
Example 1
Input ：
3
50 10
10 20
20 5
(A(BC))
Output ：
3500
analysis ：
1、 When the matrix A Columns of （column） Equal matrix B The number of rows （row） when ,A And B You can multiply .
2、 matrix C The number of rows is equal to the matrix A The number of rows ,C The number of columns is equal to B Columns of .
3、 The product of C Of the m Xing di n The elements of a column are equal to the matrix A Of the m Elements of rows and matrices B Of the n Column corresponds to the sum of the product of the elements .
The code implementation is as follows ：
while True:
try:
n = int(input())
arr = []
order = []
res = 0
for i in range(n):
arr.append(list(map(int, input().split())))
f = input()
#(A(B(C(D(E(F(GH)))))))
#（（AB）C）
for i in f:
if i.isalpha():
order.append(arr[ord(i)-65])
elif i==')' and len(order)>=2:
#print(order)
b = order.pop()
a = order.pop()
#print(a,b)
res += a[1] * b[1] * a[0]
order.append([a[0],b[1]])
print(res)
#print(order)
except Exception as e:
#print(e)
break
