高效的伊丽莎白（Elisabeth the Efficient）是一位著名的魔法师，她受东堤之地的强大领主——赋能者伊曼纽尔（Emmanuel the Empowered）之邀，为其魔法要塞增强防御。

在抵达现场并研究了要塞的结构以及保护其完整性的现有咒语后，伊丽莎白发现了所设计咒语的以下特性：

• 它应由取自字符串 $s$ 的符号组成；
• 所有符号必须唯一；
• 咒语的强度仅取决于选择了哪些符号，而与它们的顺序无关；
• 如果符号 $s_i$ 和 $s_j$（其中 $i \le j$）都存在于咒语中，则其强度增加 $d_{i,j}$。

例如，如果 $s = \text{ABC}$ 且 $$d = \begin{pmatrix} 1 & -1 & 2 \\ - & 2 & -3 \\ - & - & 1 \end{pmatrix}$$ 那么咒语 $\text{A}$ 的强度为 $1$，$\text{ABC}$ 的强度为 $2$，而 $\text{AC}$ 的强度为 $4$。

然而，这个问题对伊丽莎白来说似乎太难了，因为她几乎没有计算机方面的经验。你能帮她找到最强的咒语吗？

输入格式

输入文件的第一行包含字符串 $s$，它非空且仅包含大写拉丁字母或符号 !, ?, @, *。所有符号互不相同。因此，其长度 $n = |s|$ 不会超过 $30$。

接下来的 $n$ 行包含矩阵 $d$ 的描述。这些行中的第 $i$ 行（$1 \le i \le n$）包含 $n + 1 - i$ 个整数 $d_{i,i}, d_{i,i+1}, \dots, d_{i,n}$，由单个空格分隔。这些数字的绝对值不超过 $10^6$。

输出格式

在第一行输出最强咒语的长度。在第二行输出该咒语本身。如果存在多个强度相同的最强咒语，输出其中任意一个即可。

样例

输入 1

ABC
1 -1 2
2 -3
1

输出 1

2
AC

输入 2

@
-1

输出 2

0

输入 3

ABDFHORSU!?
1 -1 1 1 1 1 1 1 1 1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 1 1 1 1 1 1 1 -1
1 1 1 1 1 1 1 -1
1 1 1 1 1 1 -1
1 1 1 1 1 -1
1 1 1 1 -1
1 1 1 -1
1 1 -1
1 -1
-1

输出 3

9
FUSRODAH!