#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <math.h>
#include <utility>

using namespace std;



typedef struct s_man {
	int	value; // 0 is empty, 1 is wall, 2 is man
	int tx; //타겟 위치(목적지)
	int	ty;
}t_man;

typedef struct s_taxi {
	t_man* man;
	int		x;
	int		y;
	int		oil;
	int		cnt_oil;
}t_taxi;
void delivery(t_taxi taxi);
int g_n, g_m;
t_man map[20][20];
int	start_x, start_y;
int dx[] = {0,-1,1,0 };
int dy[] = {-1,0,0,1};
int g_answer = -1;

typedef struct s_cmp {
	bool operator()(t_taxi a, t_taxi b)
	{
		if (a.oil == b.oil)
		{
			if (a.y == b.y)
				return (a.x > b.x);
			return (a.y > b.y);
		}
		return (a.oil < b.oil);
	}

}t_cmp;

void find_man(int sx, int sy, int s_oil) // 승객찾기
{
	int check[20][20] = { {0} };
	priority_queue<t_taxi, vector<t_taxi>, t_cmp> pq; //문제조건 일치하게 하기위해(좌상우선)
	t_taxi taxi; // 초기 택시 생성
	taxi.x = sx; // 시작위치
	taxi.y = sy; // 시작위치
	taxi.oil = s_oil; // 시작 오일
	taxi.man = NULL; // 사람은 비어있다.
	pq.push(taxi);
	check[sy][sx] = 1;

	while(!pq.empty())
	{
		
	
		int x = pq.top().x;
		int y = pq.top().y;
		int	oil = pq.top().oil;
		if (oil < 0) //오일이 바닥났다
		{
			g_answer = -1;
			return;
		}
		if (map[y][x].value == 2) // 사람이 있으면
		{
			map[y][x].value = 0;
			t_taxi taxi;
			taxi = pq.top();
			taxi.man = &map[y][x]; // 택시에 사람을 태운다.
			delivery(taxi);
			return;
		}
		pq.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < g_n && ny >= 0 && ny < g_n)
			{
				if (check[ny][nx] == 0 && map[ny][nx].value != 1)// 벽이 아니면
				{
					check[ny][nx] = 1; // 체크배열에 체크
					t_taxi taxi; // 택시생성
					taxi.x = nx; // 다음위치
					taxi.y = ny; // 다음위치
					taxi.oil = oil - 1; // 1 줄어든 오일
					taxi.man = NULL; // 사람은 비어있다.
					pq.push(taxi);
				}
			}
		}
	}
	if (g_m != 0) // 전부 못태웠을 시
		g_answer = -1;
}

void delivery(t_taxi taxi)
{
	int tx, ty;// 목표위치
	int sx, sy; // 현재위치
	int check[20][20] = { {0} };


	tx = taxi.man->tx;
	ty = taxi.man->ty;
	sx = taxi.x;
	sy = taxi.y;
	check[sy][sx] = 1;
	queue<t_taxi> q;
	taxi.cnt_oil = 0; //승객을 배송하면서 셀 카운트
	q.push(taxi);
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int	oil = q.front().oil;
		int cnt_oil = q.front().cnt_oil;
		t_man* man = q.front().man;

		if (oil < 0) //오일이 바닥났다
		{
			g_answer = -1;
			return;
		}
		if (y == ty && x == tx) // 도착했으면
		{
			g_m -= 1;//손님 감소
			oil += (cnt_oil * 2); // 연료 보충
			g_answer = oil; // 정답 전역변수에 오일을 담자
			find_man(x, y, oil); // 다시 승객을 찾으러 간다.
			return;
		}
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < g_n && ny >= 0 && ny < g_n)
			{
				if (check[ny][nx] == 0 && map[ny][nx].value != 1)
				{
					check[ny][nx] = 1; // 체크배열에 체크
					t_taxi taxi; // 택시생성
					taxi.x = nx; // 다음위치
					taxi.y = ny; // 다음위치
					taxi.oil = oil - 1; // 1 소모된 오일
					taxi.cnt_oil = cnt_oil + 1;//배달하면서 소모된 오일
					taxi.man = man; // 사람은 그대로
					q.push(taxi);
				}
			}
		}
	}
	g_answer = -1; // 도착을 못했을시
}

int	main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	int oil;
	cin >> g_n >> g_m >> oil; // 맵 크기, 사람 수, 기름양
	for (int i = 0; i < g_n; i++)
		for (int j = 0; j < g_n;j++)
			cin >> map[i][j].value;
	cin >> start_y >> start_x;
	start_y -= 1; //0부터 시작할거기 때문
	start_x -= 1;//0부터 시작할거기 때문
	for (int i = 0; i < g_m; i++)
	{
		int x;
		int y;
		cin >> y >> x;
		y -= 1;//0부터 시작할거기 때문
		x -= 1;//0부터 시작할거기 때문
		cin >> map[y][x].ty >> map[y][x].tx; //구조체 배열에 값 삽입
		map[y][x].ty -= 1;//0부터 시작할거기 때문
		map[y][x].tx -= 1;//0부터 시작할거기 때문
		map[y][x].value = 2;
	}
	find_man(start_x, start_y, oil); // 운행 개시
	cout << g_answer;
	return (0);
}