import sys
import math
import heapq
def solve():
# Read all tokens from standard input
input_data = sys.stdin.read().split()
if not input_data:
return
out = []
idx = 0
t = int(input_data[idx])
idx += 1
for _ in range(t):
n = int(input_data[idx])
r = int(input_data[idx+1])
k = int(input_data[idx+2])
idx += 3
a = []
for i in range(n):
row = []
for j in range(n):
row.append(int(input_data[idx]))
idx += 1
a.append(row)
c = []
for i in range(n):
c.append(input_data[idx])
idx += 1
# 1. Binary search for C_M (Initial dis_M)
low = a[0][0]
high = 1000000
ans_cm = high
target = (r - 1) * n + (n - 1)
while low <= high:
mid = (low + high) // 2
if mid < a[r-1][n-1]:
low = mid + 1
continue
# BFS to check if E is reachable from (0,0) using only <= mid
q = [0]
visited = bytearray(n * n)
visited[0] = 1
reachable = False
head = 0
while head < len(q):
curr = q[head]
head += 1
if curr == target:
reachable = True
break
cy = curr // n
cx = curr % n
if cy > 0:
nxt = curr - n
if not visited[nxt] and a[cy-1][cx] <= mid:
visited[nxt] = 1; q.append(nxt)
if cy < n - 1:
nxt = curr + n
if not visited[nxt] and a[cy+1][cx] <= mid:
visited[nxt] = 1; q.append(nxt)
if cx > 0:
nxt = curr - 1
if not visited[nxt] and a[cy][cx-1] <= mid:
visited[nxt] = 1; q.append(nxt)
if cx < n - 1:
nxt = curr + 1
if not visited[nxt] and a[cy][cx+1] <= mid:
visited[nxt] = 1; q.append(nxt)
if reachable:
ans_cm = mid
high = mid - 1
else:
low = mid + 1
C_M = ans_cm
# 2. Find P_top using Left-hand wall-following rule
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
path = []
curr_y, curr_x = 0, 0
d = 1
target_y, target_x = r - 1, n - 1
steps = 0
while (curr_y, curr_x) != (target_y, target_x):
path.append(curr_y * n + curr_x)
steps += 1
if steps > 400000: # Safety break for absolute worst cases
break
for i in (-1, 0, 1, 2):
nd = (d + i) & 3
ny = curr_y + dirs[nd][0]
nx = curr_x + dirs[nd][1]
if 0 <= ny < n and 0 <= nx < n and a[ny][nx] <= C_M:
curr_y, curr_x = ny, nx
d = nd
break
else:
break
path.append(target_y * n + target_x)
# Erase cycles for simple path
simple_path = []
seen = {}
for cell in path:
if cell in seen:
cutoff = seen[cell]
while len(simple_path) > cutoff:
popped = simple_path.pop()
del seen[popped]
simple_path.append(cell)
seen[cell] = len(simple_path) - 1
P_top_cells = set(simple_path)
# 3. Setup Grid B1 and B2 Segments
B1 = []
for i in range(n): B1.append(i * n + 0)
for j in range(1, n): B1.append(0 * n + j)
for i in range(1, r): B1.append(i * n + (n - 1))
B2 = bytearray(n * n)
for j in range(n): B2[(n - 1) * n + j] = 1
for i in range(r - 1, n - 1): B2[i * n + (n - 1)] = 1
a_flat = [0] * (n * n)
c_flat = [0] * (n * n)
for i in range(n):
for j in range(n):
idx_flat = i * n + j
a_flat[idx_flat] = a[i][j]
c_flat[idx_flat] = 1 if c[i][j] == '1' else 0
# 4. Binary search for maximum dis_F
low_f = 1
high_f = 2000005
ans_f = 1
INF = 10**15
while low_f <= high_f:
X = (low_f + high_f) // 2
dist = [INF] * (n * n)
pq = []
# Setup Starting bounds B1
for start_node in B1:
av = a_flat[start_node]
if av >= X:
w = 0
else:
if X > C_M and start_node in P_top_cells:
continue
if c_flat[start_node] == 0:
continue
w = X - av
if w < dist[start_node]:
dist[start_node] = w
heapq.heappush(pq, (w, start_node))
min_cost = INF
# Run Dijkstra to find smallest 8-path bound cut linking B1 and B2
while pq:
d_u, u = heapq.heappop(pq)
if d_u > dist[u]:
continue
if B2[u]:
min_cost = d_u
break
uy = u // n
ux = u % n
for dy in (-1, 0, 1):
ny = uy + dy
if ny < 0 or ny >= n: continue
for dx in (-1, 0, 1):
if dy == 0 and dx == 0: continue
nx = ux + dx
if nx < 0 or nx >= n: continue
v = ny * n + nx
av = a_flat[v]
if av >= X:
w = 0
else:
if X > C_M and v in P_top_cells:
continue
if c_flat[v] == 0:
continue
w = X - av
new_d = d_u + w
if new_d < dist[v]:
dist[v] = new_d
heapq.heappush(pq, (new_d, v))
if min_cost <= k:
ans_f = X
low_f = X + 1
else:
high_f = X - 1
out.append(f"{C_M} {ans_f}")
print('\n'.join(out))
if __name__ == '__main__':
solve()