题解 | #矩阵乘法计算量估算# 支持括号中含有多个矩阵

import sys

# 从左到右直接计算多个矩阵相乘的乘法次数，返回次数和最后得到的矩阵行列
def get_count(ary_lists):
    make_count = 0
    left_ary = []
    for i in range(len(ary_lists)):
        if i == 0 :
            left_ary = ary_lists[i][:]
            continue
        make_count += left_ary[0]*left_ary[1]*ary_lists[i][1]
        left_ary[1] = ary_lists[i][1]
    return make_count,left_ary

# 递归运算分为第一个直接计算部分（直接调用计算函数）、第二个有括号部分和第三个剩余的可能有括号部分（都递归调用）
# 直到计算式没有括号，递归结束
# 分为两个有括号的部分是为了应对两个或多个并列括号的情况
def get_end(ary_make_info,ary_lists):
    if not '(' in ary_make_info:
        return get_count(ary_lists)
    # A(B)(C)
    start_index = ary_make_info.index('(')
    next_ary = ary_make_info[start_index+1:]
    # B的行列列表
    B = ''
    B_len = 0
    s_lists=0
    for str_index in range(start_index+1,len(ary_make_info)):
        if ary_make_info[str_index] != ')':
            B+=(ary_make_info[str_index])
            if ary_make_info[str_index] == '(':
                s_lists += 1
            else:
                B_len += 1
        else:
            if s_lists == 0:
                s_lists = str_index
                break
            else:
                B+=(ary_make_info[str_index])
                s_lists -= 1
    # C的行列列表
    C = ary_make_info[s_lists+1:]
    # A的行列列表
    A = ary_make_info[:start_index]
    A_len = len(A)
    C_len = len(ary_lists)-A_len-B_len
    A_lists = ary_lists[:A_len]
    B_lists = ary_lists[A_len:len(ary_lists)-C_len]
    C_lists = ary_lists[len(ary_lists)-C_len:]
    # 计算A需要的乘法次数
    A_make_count,A_left_ary = get_count(A_lists)
    # 计算B需要的乘法次数
    B_make_count,B_left_ary = get_end(B,B_lists)
    if len(B_left_ary) > 0:
        C_lists.insert(0,B_left_ary)
        C = 'B' + C
    if len(A_left_ary) > 0:
        C_lists.insert(0,A_left_ary)
        C = 'A' + C
    # 计算最终需要的乘法次数
    C_make_count,C_left_ary = get_end(C,C_lists)
    return A_make_count+B_make_count+C_make_count,C_left_ary

if __name__ == '__main__':
    # 按顺序计算矩阵所有乘法次数
    # 矩阵个数 例：7
    ary_number = int(input())
    ary_lists = []
    # 各个矩阵行列数 例：10 20
    for i in range(ary_number):
        ary_lists.append([int(one) for one in input().split(' ')])
    # 矩阵运算式 例：(A(BC)(DE))
    ary_make_info = input()
    all_count,_ = get_end(ary_make_info,ary_lists)
    print(all_count)