C3-Zexal的矩阵链乘

题目描述

用加括号的方式给出最优的矩阵相乘方案

输入

多组数据输入

第一行一个整数 $n$，表示矩阵链的长度（1<=n<=300）

接下来一行$n+1$个数表示这些矩阵的行数和列数

别问我为什么只有n+1个数，每相邻的两个数表示一个矩阵的大小

输出

对于每组数据，输出两行，第一行为计算次数，第二行为计算方案，用加括号的方式给出最优的矩阵相乘方案

如果不幸最优方案不唯一，选择优先计算左边的矩阵

输入样例

3
10 30 5 60
3
10 20 5 4

输出样例

4500
((A1A2)A3)
1200
((A1A2)A3)

Hint

在第二组样例中，选择((A1A2)A3)时，结果为10×20×5+10×5×4=1200

选择A1(A2A3)时，结果为20×5×4 + 10×20×4 = 1200

这时选择第一种，优先计算左边的！