두린의 아들

난쟁이 왕 소린은 겨울이 오기 전에 산속 동굴에 쌓인 금화를 최대한 많이 모으려 한다. 소린은 산 내부를 그린 지도를 손에 넣었고, 지도에는 통로와 금화가 쌓인 동굴의 위치, 그리고 각 동굴에 들어 있는 금화의 개수까지 적혀 있다.

지도는 $N \times M$ 격자다. 각 칸은 다음 문자 중 하나다.

• . 지나갈 수 있는 빈 칸
• # 벽. 들어갈 수도 없고 통과할 수도 없다
• ^ 순간이동 지점
• d 소린이 처음 서 있는 칸. 지도 전체에 정확히 하나 있다
• 0부터 9까지와 A부터 F까지 동굴. 문자를 16진수로 읽은 값이 그 동굴의 번호다. 번호는 0부터 시작하므로 0, 3, B는 각각 0번, 3번, 11번 동굴이다

소린은 시간 1마다 상하좌우로 인접한 칸 중 벽이 아닌 칸 하나로 이동한다. ^ 칸에 서 있으면 시간 1을 써서 지도의 다른 ^ 칸으로 순간이동할 수 있다. ^ 칸에서 인접한 칸으로 그냥 걸어 나가도 된다. 순간이동은 전체를 통틀어 최대 $P$번 쓸 수 있다.

동굴 칸에 들어서는 순간 그 동굴의 금화를 전부 챙긴다. 금화를 챙기는 데는 시간이 들지 않는다. 이미 비운 동굴에 다시 들어가도 금화가 더 늘지는 않는다. 같은 칸을 여러 번 지나가도 된다.

순간이동을 최대 $P$번 쓰면서 시간 $L$ 이내에 소린이 모을 수 있는 금화의 최대 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫 줄에는 네 정수 $N$, $M$, $P$, $L$이 공백으로 구분되어 주어진다 ($1 \le N, M \le 500$, $0 \le P \le 10^5$, $0 \le L \le 10^9$). $N$은 지도의 행 수, $M$은 열 수, $P$는 순간이동 횟수의 상한, $L$은 시간의 상한이다.

다음 $N$개 줄에는 각각 $M$개의 문자가 주어져 지도의 한 행을 나타낸다.

마지막 줄에는 동굴 $K$개의 금화 개수가 0번 동굴부터 차례로 공백으로 구분되어 주어진다. 각 값은 0 이상 $10^9$ 이하다. 지도에 나오는 동굴 번호는 정확히 0번부터 $K-1$번까지이고, 같은 번호가 두 번 나오지는 않는다 ($1 \le K \le 15$).

각 테스트 케이스마다 소린이 모을 수 있는 금화의 최대 개수를 한 줄에 하나씩 출력한다.