#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#define MAX_WIDTH 20
#define MAX_CUSTOMER 400
#define CUSTOMER 123

using namespace std;

typedef struct Taxi {
	int row;
	int col;
	int fuel;
} Taxi;

typedef struct Customer {
	int currentRow;
	int currentCol;
	int dstRow;
	int dstCol;
	int distance;
} Customer;

typedef struct Candidate {
	int row;
	int col;
	int fuel;
	int index;
	bool operator < (Candidate t) {
		if (fuel < t.fuel)
			return true;
		else if (fuel > t.fuel)
			return false;
		else {
			if (row < t.row)
				return true;
			else if (row > t.row)
				return false;
			else {
				if (col < t.col)
					return true;
				else
					return false;
			}
		}
	}
} Candidate;

int map[MAX_WIDTH][MAX_WIDTH];
int width, numOfCustomer;
Taxi taxi;
Customer customer[MAX_CUSTOMER];


//nxn 크기 맵에 각 칸엔 벽 또는 빈칸
//빈칸엔 승객과 택시가 올 수 있음
//m 명을 태워야하고, m명은 각각 흩어져 있음
//현재 택시위치에서 가장 가까운 승객을 태우고, 여러명이면 행이 작고, 열이 작은 승객 먼저
//택시와 승객이 같은 위치면 0, 승객을 성공적으로 태워다주면, 태워다주느라 소모한 연료의 두배가 충전됨.
//태우는 도중에 연료가 소진되면 그걸로 업무 종료. 도착과 동시에 소진은 괜찮다.
//승객을 태우러 가는 도중에도 연료는 소모된다.

int startWork();
void getCustomerDistance();
bool check();

int main() {
	cin >> width >> numOfCustomer >> taxi.fuel;
	for (int i = 0; i < width; i++) {
		for (int j = 0; j < width; j++)
			cin >> map[i][j];
	}
	cin >> taxi.row >> taxi.col;
	taxi.row--;
	taxi.col--;
	for (int i = 0; i < numOfCustomer; i++) {
		cin >> customer[i].currentRow >> customer[i].currentCol >> customer[i].dstRow >> customer[i].dstCol;
		customer[i].currentRow--;
		customer[i].currentCol--;
		customer[i].dstRow--;
		customer[i].dstCol--;
		customer[i].distance = -1;
		map[customer[i].currentRow][customer[i].currentCol] = CUSTOMER + i;
	}
	getCustomerDistance();
	if (check())
		cout << startWork();
	else
		cout << -1;
}

void getCustomerDistance() {
	for (int i = 0; i < numOfCustomer; i++) {
		bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
		list<Taxi> q;
		vector<int> candidate;
		q.push_back({ customer[i].currentRow, customer[i].currentCol, 0 });
		visit[customer[i].currentRow][customer[i].currentCol] = true;

		while (!q.empty()) {
			Taxi temp = q.front();
			q.pop_front();

			if (temp.row == customer[i].dstRow && temp.col == customer[i].dstCol) {
				customer[i].distance = temp.fuel;
				break;
			}

			if (temp.row != 0 && map[temp.row - 1][temp.col] != 1 && !visit[temp.row - 1][temp.col]) {
				q.push_back({ temp.row - 1, temp.col, temp.fuel + 1 });
				visit[temp.row - 1][temp.col] = true;
			}
			if (temp.row != width - 1 && map[temp.row + 1][temp.col] != 1 && !visit[temp.row + 1][temp.col]) {
				q.push_back({ temp.row + 1, temp.col, temp.fuel + 1 });
				visit[temp.row + 1][temp.col] = true;
			}
			if (temp.col != 0 && map[temp.row][temp.col - 1] != 1 && !visit[temp.row][temp.col - 1]) {
				q.push_back({ temp.row, temp.col - 1, temp.fuel + 1 });
				visit[temp.row][temp.col - 1] = true;
			}
			if (temp.col != width - 1 && map[temp.row][temp.col + 1] != 1 && !visit[temp.row][temp.col + 1]) {
				q.push_back({ temp.row, temp.col + 1, temp.fuel + 1 });
				visit[temp.row][temp.col + 1] = true;
			}
		}
	}
}

bool check() {
	for (int i = 0; i < numOfCustomer; i++)
		if (customer[i].distance == -1)
			return false;
	return true;
}

int startWork() {
	for (int i = 0; i < numOfCustomer; i++) {
		//가장 가까운 승객 뽑아서 밑 변수에 저장.
		Customer crtCustomer;
		int crtCustomerDistance = 0;
		if (map[taxi.row][taxi.col] >= CUSTOMER)
			crtCustomer = customer[map[taxi.row][taxi.col] - CUSTOMER];
		else {
			bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
			visit[taxi.row][taxi.col] = true;
			list<Taxi> q;
			q.push_back({ taxi.row, taxi.col, 0 });
			vector<Candidate> candidate;

			while (!q.empty()) {
				Taxi temp = q.front();
				q.pop_front();

				if(map[temp.row][temp.col] >= CUSTOMER)
					candidate.push_back({ temp.row , temp.col, temp.fuel, map[temp.row][temp.col] - CUSTOMER });

				if (temp.row != 0 && map[temp.row - 1][temp.col] != 1 && !visit[temp.row - 1][temp.col]) {
					q.push_back({ temp.row - 1, temp.col, temp.fuel + 1 });
					visit[temp.row - 1][temp.col] = true;
				}
				if (temp.row != width - 1 && map[temp.row + 1][temp.col] != 1 && !visit[temp.row + 1][temp.col]) {
					q.push_back({ temp.row + 1, temp.col, temp.fuel + 1 });
					visit[temp.row + 1][temp.col] = true;
				}
				if (temp.col != 0 && map[temp.row][temp.col - 1] != 1 && !visit[temp.row][temp.col - 1]) {
					q.push_back({ temp.row, temp.col - 1, temp.fuel + 1 });
					visit[temp.row][temp.col - 1] = true;
				}
				if (temp.col != width - 1 && map[temp.row][temp.col + 1] != 1 && !visit[temp.row][temp.col + 1]) {
					q.push_back({ temp.row, temp.col + 1, temp.fuel + 1 });
					visit[temp.row][temp.col + 1] = true;
				}
			}
			if (candidate.size() == 0)
				return -1;
			sort(candidate.begin(), candidate.end());
			crtCustomer = customer[candidate[0].index];
			crtCustomerDistance = candidate[0].fuel;
		}

		//가장 가까운 승객을 데리고, 연료 충분한지, 충분하면 이동시킴
		map[crtCustomer.currentRow][crtCustomer.currentCol] = 0;
		int distance = crtCustomer.distance + crtCustomerDistance;
		if (distance <= taxi.fuel) {
			taxi.row = crtCustomer.dstRow;
			taxi.col = crtCustomer.dstCol;
			taxi.fuel -= distance;
			taxi.fuel += (2*crtCustomer.distance);
		}
		else
			return -1;
	}

	return taxi.fuel;
}