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

import re
import random



def cal(list1, list2):
    list3 = [list1[0], list2[1]]
    num = list1[0]*list1[1]*list2[1]

    return [list3, num]




while True:
    try:
        n = int(input())

        # 逐个获取矩阵并存储为列表
        list_in = []
        for i in range(n):
            list_in.append(list(map(int, input().split(' '))))

        # # 接受表达式 存入字典
        # text = input()
        # index = 0
        # dict_ = {}
        # for tmp in text:
        #     if re.match(r'[A-Z]', tmp):
        #         dict_[tmp] = list_in[index]
        #         index+=1
        # # print(dict_)

        # 接受表达式 把字母替换为矩阵
        text = list(input())
        index = 0
        for i in range(len(text)):
            if re.match(r'[A-Z]', text[i]):
                text[i] = list_in[index]
                index+=1
        # print(text)

        # 找到最右左括号 计算并删除括号 返回计算结果替换原段落 循环 直至列表长度变为1
        num = 0
        # 计算运算次数
        key = 0
        # 防死循环
        # print(text)
        while True and key < n:
            # print(key)
            done = False
            for i in range(len(text)-1,0,-1):
                # print(f'i = {i}')
                # print(f'text[i] = {text[i]}')
                # 找最右的左括号
                # 注意这样无法检测到首位
                tmp = []
                if text[i] == '(':
                    done = True
                    # 找到右括号确定范围
                    for j in range(i+1, len(text)):
                        # print(f'i = {i} j = {j}')
                        tmp = text[i:j+1]
                        # print(f"tmp = {tmp}")
                        if text[j] == ')':
                            # 开始计算
                            if len(tmp) <= 2:
                                # 非法输入 空括号
                                # 替换并返回
                                for k in range(j-i+1):
                                    # 注意pop后索引会变
                                    # 遍历用次数 pop索引应固定
                                    text.pop(i)
                            elif len(tmp) == 3:
                                # 括号内只有一个矩阵 直接弹掉括号进行返回
                                text.pop(j)
                                text.pop(i)
                            else:
                                # 括号内有多个矩阵
                                tmp_cal = tmp[1]
                                # 取出首个矩阵
                                for tmp_m in tmp[2:-1]:
                                    # print(f'tmp_m = {tmp_m}')
                                    [tmp_cal,num_cal] = cal(tmp_cal, tmp_m)
                                    num+=num_cal
                                # print(f'tmp_cal:{tmp_cal}')
                                # print(f'num: {num}')

                                for k in range(j-i):
                                    # 注意pop后索引会变
                                    # 遍历用次数 pop索引应固定
                                    # pop掉段落长度-1 剩一个右括号位置不变 用新矩阵替换
                                    text.pop(i)
                                    # print(text)
                                text[i] = tmp_cal
                                # print(text)
                                # 返回最终矩阵
                                # print(text)
                            break
                    break
            if not done:
                # 当首位以后的位置找不到右括号
                if text[0] == '(' and '(' not in text[1:]:
                    # 开始计算
                    # 替换并返回 
                    # 括号内有多个矩阵
                    tmp = text
                    tmp_cal = tmp[1]
                    # 取出首个矩阵
                    for tmp_m in tmp[2:-1]:
                        # print(f'tmp_m = {tmp_m}')
                        [tmp_cal,num_cal] = cal(tmp_cal, tmp_m)
                        num+=num_cal
                    # print(f'tmp_cal:{tmp_cal}')
                    # print(f'num: {num}')

                    for k in range(len(text)-1):
                        # 注意pop后索引会变
                        # 遍历用次数 pop索引应固定
                        # pop掉段落长度-1 剩一个右括号位置不变 用新矩阵替换
                        text.pop(0)
                        # print(text)
                    text[0] = tmp_cal
                    # print(text)
                    # 返回最终矩阵
                    # print(text)
                    break
            key += 1
        print(num)

        # # 测试括号功能
        # text2 = '(0(12)(34(5(6)))7(8)9)'
        # print(text2)

        # # 按括号拆成单元 计算最右的左括号所在的対 依次向左
        # # 最右括号必为最下级括号（若非最下级则该括号对应有内嵌括号，则不为最右左括号対 矛盾）计算完后取消括号 并迭代 依然成立最右括号必为最下级括号
        # indexs = [tmp.start() for tmp in re.finditer(r'\(', text)]
        # indexs.reverse()
        # # print(indexs)      
        
        # indexs_2 = []
        # for tmp in indexs:
        #     tmp2 = 0
        #     start = tmp
        #     while True:
        #         tmp2 = text.find(')', start)
        #         # print(f"tmp={tmp} tmp2={tmp2}")
        #         if tmp2 in indexs_2:
        #             start = tmp2+1
        #         else:
        #             indexs_2.append(tmp2)
        #             break

        # # print(indexs)
        # # print(indexs_2)
        # for i in range(len(indexs)):
        #     print(text[indexs[i]:indexs_2[i]+1])
        # # print(indexs)
        # # print(indexs_2)
    except:
        break