题解 | #矩阵乘法计算量估算#

# Read
n = int(input())
inList = []
for _ in range(n):
    inList.append(list(map(int, input().strip().split())))
seq = list(input())
# init
rest, buf = [], []
count = 0
# A(3,2) B (2,4) ==> 3 * 4 * 2 = 24 
# A (50, 10), B(10*20),   C(20*5)
# ((AB)C) == 50*20*10 + 50 * 20 * 5 = 15000
# A(BC) == 10 * 20 * 5 + 50 * 10 * 5 = 2500 + 1000 = 3500
#### if have ABC or more like ABCDE, it is still works.
def get_matrix_mul_count(mList):
    count = 0
    A = mList.pop(0)
    while mList:
        B = mList.pop(0)
        count += A[0] * A[1] * B[1]
        A = [A[0],B[1]]
    return A, count
# pop and push 
while seq:
    i = seq.pop(0)
    if i != ")":
        if i == "(":
            rest.append(i)
        else:
            rest.append(inList[ord(i) - ord("A")])
        continue
	# collect inner op block.
    while rest[-1] != "(":
        t = rest.pop(-1)
        buf.insert(0, t)
    rest.pop(-1)
	# count and keep the calcuted matrix shape.
    A, curCount = get_matrix_mul_count(buf)
    count += curCount
    rest.append(A)

if len(rest) > 1:
   A, curCount = get_matrix_mul_count(rest)
   count += curCount
print(count)