小丑的身份证和复印件
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

你作为一名游客来到了著名的哥谭市旅游,无意中却不小心弄丢了自己的身份证和复印件。一开始你抱有些希望,认为身份证和复印件被人诚实地捡到了,可以寻回。不过,在你寻找了不少地方之后,你意识到这场寻找的旅程将会比你想象中的要困难得多。

经过不断的打听和搜索,你得知这些证件碎片已经散落在了整个哥谭市内的不同角落中或者已经消失,令人十分无助。令你心情更加沮丧的是,这些证件碎片的字母并不是完整的,而是分别只有五个字母,分别是身份证的五个字母J、O、K、E、R,和复印件的五个字母j,o,k,e,r。 这让你觉得自己像是在玩一场需要寻找完整单词的游戏。

你感到自己陷入了困境,时间也在流逝。但无论如何,你依然想办法继续尝试着去找寻这些碎片。在一家咖啡店中喝咖啡时,你突然想到了一个办法,你可以挨个地走访哥谭市的大街小巷,在街边寻找印刷工厂和复印店,寻找与这些字母有关的信息。这么做虽然步骤繁琐,但这是你唯一能想到的方法。所以你开始了一段漫长而寻找的旅程。

现在给你一张 n \times m 的字符矩阵图表示哥谭市,保证你的身份证和复印件在哥谭市地图中。在图中,每一次移动,只能上下左右进行移动一个单位的距离,消耗一个单位的时间,能重复移动到已经经过的地点,但是同一个地点的碎片只能拾起一次。

图中字符集:

# :表示围墙或障碍物,你不能通过。

( :表示你现在的位置,图中只会出现一次。

) :表示飞机机场的位置,图中只会出现一次。

A-Z,a-z:表示地图中该位置所拥有的字母碎片,可以重复经过此地。

由于时间问题,你需要花最少的时间找齐你的身份证和复印件碎片并赶往飞机机场乘坐飞机回家。请你计算出你所需要花费的最小时间。若无法找齐你的身份证和复印件碎片或者无法移动移动到飞机场,输出 -1

输入描述:

第一行,两个正整数 n(2 \leq n \leq 100),m(2 \leq m \leq 100),表示哥谭市地图尺寸。

接下来 n 行,每行 m 个字符,表示哥谭市地图。

输出描述:

一行,表示答案。
示例1

输入

复制
2 10
(JOKERjoke
#####asdr)

输出

复制
12