第九重迷宫

题目描述

Hikari 醒了，她从醒来的时候就感觉良好。

这是道使人愉快的风景线。

长久以来，她行走于这荒芜却又美丽的世界，赞扬着她所找到的新鲜事物。

长久以来，她带领着那些玻璃碎片一同旅行，以至于天空已经变为一面弯曲的镜子，反射出了她所能见到的最遥远的光芒。

围绕着那第九重迷宫的是闪闪发光的回忆碎片，如同一片不断变化的海洋。当她步入迷宫的时候，那片海洋开始推向两边。

她开始仔细地端详起每块承载着不同回忆的碎片。每当她走到迷宫的一处，拾起一块碎片，碎片便会飘起，融入了她头顶的那片天空。在她收集了她所能收集到的最后一块碎片后，所有的碎片便按照她找到它们的顺序，融合成了蕴含记忆的韵律源点 —— Arcaea.

Hikari 决心开始追溯那些美好的回忆，尽管她不知道这些回忆终会将她吞噬。

第九重迷宫可以抽象成一个 \(n \times m\) 的矩阵，没有起点也没有终点。矩阵的每个格子可能是障碍物或者通路，通路中包含了一块回忆值为 \(1 \sim 9\) 的碎片。Hikari 可以从第九重迷宫的**任意一个通路格子**出发，每次可以沿上、下、左、右四个方向走一个格子（但不能走到障碍物中，也不能重复走一个通路格子）。

Hikari 醒来的时候，她没有任何回忆。她每拾得一片碎片，这片碎片的回忆值就会融入到她已有的回忆中。假设她已经获得回忆值为 \(a_1a_2a_3a_4...a_i\)，此时她拾得了一片回忆值为 \(a_k\) 的碎片，那么她拥有的回忆值将变为 \(a_1a_2a_3a_4...a_ia_k\).

Hikari 想要追溯到尽可能多的回忆，所以她希望当她收集完她能收集的最后一块碎片之后，所得到的回忆值最大，请你告诉她所能获得的最大的回忆值。

除了追溯尽可能多的回忆之外，Hikari 希望收集到尽可能纯粹的回忆，因此她会将收集的回忆值与整个迷宫包含的回忆值比较，以评估她所收集的回忆是否为纯粹的。整个迷宫包含的回忆值定义为：迷宫中包含的所有碎片（不管它们能否到达）的权值，从小到大排序并融合所得的值。具体地，如果迷宫中含有 \(n\) 块碎片，按权值从小到大排序后为 \(a_1, a_2, ..., a_n\)，那么整个迷宫包含的回忆值为 \(a_1a_2...a_n\). 注意，Hikari 实际收集的回忆值可能溢出迷宫包含的回忆值。

输入格式

每个测试点包含多组数据。

第一行是一个整数 \(T (T < 10)\)，表示当前测试点的数据组数。

每组数据的第一行是两个整数 \(n, m\) (\(2 \le n, m \le 20\))，表示第九重迷宫的长和宽。

接下来有 \(n\) 行，每一行包含 \(m\) 个字符，描述迷宫的信息。每个字符可能是一个 #（表示这一格为障碍物）或是一个 \(1 \sim 9\) 的数字（表示这一格为通路，且包含了权值为所给数字的回忆碎片）。

所有数据都保证包含碎片的格子数不超过 \(50\), Hikari 所能走过的最长通路的长度不会超过 \(40\).

输出格式

对于每组输出数据，输出两行。

第一行输出 Hikari 所能获得的最大回忆值。

第二行输出 PURE MEMORY, FULL RECALL, TRACK COMPLETE 或 TRACK LOST，规则如下：

• 如果 Hikari 收集的回忆值大于迷宫包含的回忆值，则输出 PURE MEMORY
• 如果 Hikari 收集的回忆值恰好等于迷宫包含的回忆值，则输出 FULL RECALL
• 如果 Hikari 收集的回忆值小于迷宫包含的回忆值，但大于等于整个迷宫包含的回忆值的 70%，则输出 TRACK COMPLETE
• 如果 Hikari 收集的回忆值小于整个迷宫包含的回忆值的 70%，则输出 TRACK LOST

输入样例

4
5 5
#####
#123#
#654#
#789#
#####
4 4
####
#77#
#77#
7777
3 5
12345
####8
#1###
3 5
##451
####4
#1#1#

输出样例

987654321
PURE MEMORY
77777777
FULL RECALL
854321
TRACK COMPLETE
4514
TRACK LOST

样例解释

样例包含 4 组子数据。每组样例输出的第一行是 Hikari 能够获得的最大回忆值。

第一组子数据中，第九重迷宫中包含的回忆值为 123456789，而 Hikari 能够获得的最大回忆值为 987654321，大于迷宫所包含的回忆值，输出 PURE MEMORY.

第二组子数据中，第九重迷宫中包含的回忆值为 77777777，而 Hikari 能够获得的最大回忆值为 77777777，等于迷宫所包含的回忆值，输出 FULL RECALL.

第三组子数据中，第九重迷宫中包含的回忆值为 1123458，而 Hikari 能够获得的最大回忆值为 854321，大于迷宫所包含的回忆值的 70%，输出 TRACK COMPLETE.

第四组子数据中，第九重迷宫中包含的回忆值为 111445，而 Hikari 能够获得的最大回忆值为 4514，小于迷宫所包含的回忆值的 70%，输出 TRACK LOST.

子任务及数据规模

如果你难以解决整道题目，你可以尝试解决部分测试点。

测试点编号	\(n, m\)	特殊限制	分值
1	\(2 \le n, m \le 6\)	包含回忆碎片的格子不超过 6 个	6
2	\(2 \le n, m \le 6\)	包含回忆碎片的格子不超过 9 个	6
3	\(2 \le n, m \le 10\)	包含回忆碎片的格子不超过 9 个	6
4	\(2 \le n, m \le 10\)	Hikari 能走过的最长通路长度不超过 9	6
5	\(2 \le n, m \le 10\)	包含回忆碎片的格子不超过 16 个	6
6	\(2 \le n, m \le 10\)	包含回忆碎片的格子不超过 16 个	7
7	\(2 \le n, m \le 10\)	包含回忆碎片的格子不超过 16 个	7
8	\(2 \le n, m \le 10\)	包含回忆碎片的格子不超过 16 个	7
9	\(2 \le n, m \le 10\)	Hikari 能走过的最长通路的长度不超过 16	7
10	\(2 \le n, m \le 10\)	Hikari 能走过的最长通路的长度不超过 16	7
11	\(2 \le n, m \le 12\)	无特殊限制	7
12	\(2 \le n, m \le 16\)	无特殊限制	7
13	\(2 \le n, m \le 16\)	数据有梯度	7
14	\(2 \le n, m \le 20\)	无特殊限制	7
15	\(2 \le n, m \le 20\)	无特殊限制	7