닌자 레전드

닌자는 일본 중세의 전문 스파이다. 영화와 게임에서는 뛰어난 신체 능력을 가진 모습으로 자주 등장한다.

당신은 닌자 게임 Ninja Legend를 하고 있다. 이 게임에서는 재능이 뛰어난 닌자 Master Ninja를 조종해 여러 임무를 완수한다. 한 임무에서 닌자는 저택에 몰래 들어가 금 조각을 최대한 많이 훔쳐야 한다. 저택에는 함정이 많아서 쉽지 않다. 닌자가 함정에 빠지면 저택 주인에게 잡히기를 기다리는 수밖에 없고, 이는 임무 실패를 뜻한다. 그러니 좋은 전략으로 닌자를 조종해야 한다.

저택 내부는 아래와 같은 격자 지도다. Master Ninja는 입구로 들어가서 입구로 나온다. 그는 상하좌우 네 방향으로 바닥 칸을 따라 움직일 수 있다. 금 블록이 놓인 칸에 들어서면 금 블록을 주울 수 있다. 하지만 나중에 그 칸을 다시 방문했을 때 주워도 되고, 아예 줍지 않아도 된다.

그림 1: 지도 예시

닌자에게는 함정에 대처하는 특별한 능력이 있다. 이동 모드는 일반 모드와 대시 모드 두 가지다. 처음에는 일반 모드다. 금 블록을 줍지 않고 같은 방향으로 두 칸 연속 이동하면 대시 모드가 된다. 방향을 바꾸거나, 금 블록을 줍거나, 아래에서 설명하는 벽 달리기를 하면 일반 모드로 돌아간다. 닌자는 함정 하나를 뛰어넘을 수 있다. 대시 모드에서는 진행 방향에 있는 함정 두 개를 뛰어넘을 수 있다. 또한 대시 모드에서는 벽을 달려 진행 방향의 함정을 최대 네 개까지 넘을 수 있다. 벽 달리기를 하려면 지나는 칸과 출발 및 도착 바닥 칸에 인접한 벽 칸이 연속으로 있어야 한다. 벽 달리기를 하면 일반 모드로 돌아간다.

아래 그림의 왼쪽은 닌자가 벽을 달리는 모습이다. 오른쪽은 벽을 달려도 함정을 넘을 수 없는 경우다.

그림 2: 벽 달리기

그림 3: 연속되지 않은 벽

닌자가 얻을 수 있는 금 블록의 최대 개수와, 그 금 블록들을 얻는 데 드는 최소 비용을 구하고 싶다. 이를 구하는 프로그램을 작성하라. 칸에서 인접한 칸으로 한 번 이동하는 데 비용 1이 든다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 첫 줄에는 저택의 높이 $H$ ($3 \le H \le 60$)와 너비 $W$ ($3 \le W \le 80$)를 나타내는 정수 두 개가 주어진다. 이어지는 $H$개의 줄에는 각각 $W$개의 문자가 있다. 각 문자는 다음 중 하나다. '%' (입구), '#' (벽), '.' (바닥), '^' (함정), '*' (금 블록이 있는 바닥).

금 블록의 개수는 15 이하이며, 모든 지도는 벽 칸으로 둘러싸여 있다.

입력의 끝은 0 두 개가 한 줄에 적힌 줄로 나타낸다.

각 데이터셋에 대해 얻을 수 있는 금 블록의 최대 개수와 최소 비용을 한 줄에 출력한다. 닌자가 금 블록을 하나도 얻을 수 없다면 대신 0 0을 출력한다. 다른 문자는 출력하지 않는다.