题目背景

经过勇气GG的第二次不懈努力，三仙兽终于完成了风灵的谜题，依靠御风飞翔之术越过了大河。北京距离他们只有一步之谣了……

题目描述

三仙兽现在位于的地方，是连接古代和现代两个世界的结界法阵。一般来说，即使是神也是不能跨越时空的，但是，风灵给了他们一点提示，告诉了他们这个法阵的玄机。并告诉三兽，只要同心协力，就可以改变命运，突破结界的枷锁。

风灵递给他们一张地图，这个地图是方形的，上面画出了法阵中的各个关键区域，每一个区域都是方形，用一个字符来表示。

要破解这个法阵，必须由三人站在三个不同的区域内，心神合一，同时施法半个时辰，方能化解。

在这个法阵中移动是相当消耗水分的，因此他们必须携带一定量的水，他们的身旁有一口喷泉，因而水源可以认为是无限的。但是，风灵又告诉他们：三仙兽必须携带尽可能少的水量，如果从喷泉中汲取的水过多，否则神就会发怒，封印住这整个法阵。

现在勇气拿着这个地图找到你，你可以帮他算出他最少需要携带多少水吗？

在区域中行进时，只能朝上下左右四个方向移动，当从 A 区域走到 B 区域时，所需要的水量为 B 区域类型需要的水量乘以当前在队兽数。

到达其中一仙兽的目的地时，那一只仙兽（必须）留下，由其他仙兽继续行进，并由继续前进的仙兽携带水。由于仙兽不移动时消耗水量是很小的，所以你可以认为不需要为留下的仙兽准备水。

三仙兽进入目的地时不需要消耗水，并且里面有一口小小的水井，可以让继续前进的每个仙兽都携带一个单位的水。即如果三个仙兽走到一个目的地，除了不需要消耗水之外，其中一个留下，另外两个可以各多携带一个单位的水，这样总的相当与水量多了两个单位。但当他们再次来到这个目的地时，这里则当作普通的平地（即每仙兽消耗一单位水）。

另外地图中可能有一些区域（用水量视为平地）存在机关，只能由某个仙兽解决，这样则必须是这个仙兽在队时才能通过这个区域，由于解决机关需要体力，还需要多消耗一单位水量。注意：这种区域走过一次之后并不会变回平地，下次经过时（如果需要的话）还必须有对应的仙兽在队。

地图中的字符含义如下：

. 平地，每仙兽消耗一单位水。

^ 丘陵，每仙兽消耗两单位水。

~ 沙漠，每仙兽消耗三单位水。

A、B、C 对应花楹、蓬絮和勇气的目的地区域。

a、b、c 只能花楹、蓬絮和勇气在队时通过的区域。每仙兽消耗一单位水，再附加一单位水消耗。

# 不能通过的区域。

S 三仙兽的起始点，地形视为平地。

除此之外，勇气还有一种特殊的传送技，可且最多只可使用一次，可以带所有人朝四个方向跳过一个区域（使用法术不消耗水，只算进入的区域的水量消耗，跳过的区域不算，可以通过这个法术跳过不能通过的区域），当然，使用这个技能时勇气必须在队，并且进入的区域也必须是可进入的（例如，不能是对应仙兽不在队的机关区域）。

数据范围

10% 的数据中只会出现 S、A、B、C 和 .，且 A、B 和 C 连在一起

30% 的数据中只会出现 S、A、B、C、# 和 .

60% 的数据中不会出现 a、b、c

100% 的数据中，所有区域符号均可能出现

60% 的数据中，n <= 10

100% 的数据中，n <= 30

第一行一个正整数 n，表示地图的大小为 n*n。

第二行至第 n + 1 行，每一行 n 个字符，表示地图。

一行，一个整数，表示至少需要携带的水量。

样例解释

向上使用传送术，再向上走，之后左走三次即可。