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

import sys

"""
(A(BC)) = (A_{p,m}(B_{m,n}C_{n,q}))
关键1: 乘法次数 = m*n*q + p*m*q
关键2: 识别括号; list.pop(*) 实现出栈,list.append(*) 实现入栈
"""

while True:
    try:
        arr_n = int(input())
        dim_pair_list = []
        for i in range(arr_n):
            dim_pair_list.append(list(map(int, input().split())))  # 第i组行数->空格->列数->回车
        arr_series = input()  # (A(BC))
        
        keys_str = arr_series.replace("(", "").replace(")", "")  # replace方法不会改变原字符串
        dim_pair_dict = dict(zip(keys_str, dim_pair_list))  # 不必假设矩阵ABCDEF顺序出现

        arr_list = []  # 栈
        multi_num = 0
        for i_char in arr_series:
            if i_char != ")":
                arr_list.append(i_char)
            else:
                C_label = arr_list.pop()
                B_label = arr_list.pop()
                arr_list.pop()  # 删除 '('
                multi_num += (
                    dim_pair_dict[B_label][0]
                    * dim_pair_dict[B_label][1]
                    * dim_pair_dict[C_label][1]
                )

                dim_pair_dict[B_label] = [
                    dim_pair_dict[B_label][0],
                    dim_pair_dict[C_label][1],
                ]
                arr_list.append(B_label)
        print(multi_num)
    except:
        break