题目描述

高效的伊丽莎白（Elisabeth the Efficient）是一位著名魔法师。强大的伊曼纽尔（Emmanuel the Empowered）——东岸诸国的领主——邀请她增强自己魔法堡垒的防护。

在考察堡垒结构和已有防护法术后，伊丽莎白发现，要设计的咒语具有以下性质：

• 咒语只能使用字符串 $s$ 中出现的符号；
• 咒语中的所有符号必须互不相同；
• 咒语的强度只取决于选择了哪些符号，与这些符号的排列顺序无关；
• 若符号 $s_i$ 和 $s_j$（$i\le j$）都出现在咒语中，则咒语强度增加 $d_{i,j}$。

例如，若

$$s=\texttt{ABC},\qquad d=\begin{pmatrix} 1&-1&2\\ &2&-3\\ & &1 \end{pmatrix},$$

则咒语 A 的强度为 $1$，咒语 ABC 的强度为 $2$，咒语 AC 的强度为 $4$。

这个问题对计算机经验不多的伊丽莎白来说太困难了。请帮助她找出强度最大的咒语。

空咒语也是合法的，其长度和强度均为 $0$。

输入格式

第一行包含一个非空字符串 $s$。字符串只可能包含：

• 大写英文字母 A～Z；
• 符号 !、?、@、*。

$s$ 中所有字符两两不同。令 $n=|s|$，因此 $n\le 30$。

接下来 $n$ 行描述矩阵 $d$ 的上三角部分。

第 $i$ 行（$1\le i\le n$）包含 $n+1-i$ 个整数：

$$d_{i,i},d_{i,i+1},\ldots,d_{i,n}.$$

所有数的绝对值均不超过 $10^6$。

输出格式

第一行输出最强咒语的长度。

第二行输出该咒语本身。如果存在多个强度相同的最优咒语，输出任意一个均可；咒语中字符的顺序任意。

由于答案可能不唯一，本题必须使用 SPJ 检查输出咒语是否合法且达到最优强度。

样例 1

输入

ABC
1 -1 2
2 -3
1

输出

2
AC

样例 2

输入

@
-1

输出

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

输出

9
FUSRODAH!