#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <functional> // Required for std::greater

using namespace std;

// Use long long for time and fatigue values, as they can be large or negative.
typedef long long ll;

// Using pair to store {fatigue, time}.
// std::pair comparison is lexicographical by default: compares first element, then second if first are equal.
// This naturally prioritizes minimum fatigue, then minimum time.
using StateInfo = pair<ll, ll>; 

// Define a large constant to represent infinity. Must be large enough to avoid overflow
// when adding costs but greater than any possible finite path cost.
// Max fatigue/time change could be roughly NM * max(C_i or D_i) approx 6400 * 10^9 = 6.4 * 10^12.
// 4e18 (4 * 10^18) is safely within the range of signed 64-bit integers and large enough.
const ll INF = 4e18; 

// Define the state key for the distance map. It uniquely identifies a state by
// the number of rewinds used (k) and the location (row r, column c).
// Using pair<int, pair<int, int>> format: {k, {r, c}}.
using StateKey = pair<int, pair<int, int>>; 

// Structure to represent a state in the priority queue.
// Contains the StateInfo {fatigue, time} and the StateKey {k, {r, c}}.
struct PQState {
    StateInfo info; // {fatigue, time}
    StateKey key;   // {k, {r, c}}

    // Custom comparator for the priority queue to make it a min-heap based on StateInfo.
    // `std::priority_queue` by default is a max-heap. Using `std::greater` makes it a min-heap.
    // We want to extract the state with the minimum fatigue first. If fatigue levels are equal,
    // extract the one with minimum time. This matches the lexicographical comparison of `std::pair`.
    bool operator>(const PQState& other) const {
        // This defines the order for the min-heap. `a > b` means `a` has lower priority than `b`.
        // Check fatigue first.
        if (info.first != other.info.first) {
            return info.first > other.info.first; // Higher fatigue means lower priority
        }
        // If fatigue is equal, check time.
        return info.second > other.info.second; // Higher time means lower priority
    }
};

// Global variables for grid dimensions, number of mysterious squares, and time limit.
int N, M, K;
ll T_limit; // Target time limit
// Map to store mysterious squares data: key {r, c}, value {C, D}
map<pair<int, int>, pair<ll, ll>> mysterious_squares; 

// Deltas for moving to adjacent squares: Up, Down, Left, Right
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input values
    cin >> N >> M >> K >> T_limit;

    // Read mysterious square data
    for (int i = 0; i < K; ++i) {
        int r, c;
        ll C, D;
        cin >> r >> c >> C >> D;
        // Input coordinates are 1-based
        mysterious_squares[{r, c}] = {C, D};
    }

    // Set maximum number of rewinds to consider. Based on the pigeonhole principle argument:
    // If an optimal path uses more than NM rewinds, it must contain a cycle. Analysis shows
    // we can potentially limit the number of "base" rewinds to NM.
    int max_k = N * M; 

    // Use std::map to store the minimum {fatigue, time} found so far for each state {k, {r, c}}.
    // This is more memory-efficient than a dense 3D array if many states are unreachable.
    map<StateKey, StateInfo> dist;

    // Priority queue for Dijkstra's algorithm. Stores PQState objects. Uses the custom comparator `operator>`.
    priority_queue<PQState, vector<PQState>, greater<PQState>> pq;

    // Initial state: At square (1, 1), 0 rewinds used, fatigue 0, time 0.
    StateKey start_key = {0, {1, 1}};
    dist[start_key] = {0, 0}; // Record distance to start state
    pq.push({{0, 0}, start_key}); // Push the start state into the priority queue

    // Variable to track the minimum fatigue found for reaching the goal (N, M) within the time limit T_limit.
    ll min_fatigue_at_goal = INF;

    // Main loop of Dijkstra's algorithm
    while (!pq.empty()) {
        // Extract the state with the lowest priority {fatigue, time} from the priority queue.
        PQState current = pq.top();
        pq.pop();

        StateInfo current_info = current.info; // {fatigue, time} of the current state
        StateKey current_key = current.key;    // {k, {r, c}} of the current state
        
        ll f = current_info.first;   // current fatigue
        ll t = current_info.second;  // current time
        int k = current_key.first;     // current number of rewinds
        int r = current_key.second.first; // current row
        int c = current_key.second.second;// current column

        // Check if the extracted state is outdated. This happens if we've already found a
        // better path to this state {k, r, c} since this state was pushed into the PQ.
        // We compare the extracted state's info `current_info` with the stored info `dist[current_key]`.
        // If `current_info` is lexicographically greater, it means it's worse (higher fatigue or same fatigue but higher time).
        auto it = dist.find(current_key);
        // If the key isn't in dist map (should not happen with this logic, but safe check) or info is worse than stored
        if (it == dist.end() || current_info > it->second) { 
             continue; // Skip processing this outdated state
        }
         
        // Explore Move actions to adjacent squares
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i]; // Calculate neighbor row
            int nc = c + dc[i]; // Calculate neighbor column

            // Check if the neighbor coordinates are within the grid boundaries [1..N, 1..M]
            if (nr >= 1 && nr <= N && nc >= 1 && nc <= M) {
                // Move action: fatigue 'f' remains unchanged, time 't' increases by 1.
                StateInfo next_info = {f, t + 1};
                // Number of rewinds 'k' also remains unchanged.
                StateKey next_key = {k, {nr, nc}};

                // Check if the path through the current state to the neighbor state {k, nr, nc}
                // is better (lexicographically smaller {fatigue, time}) than any path found so far.
                auto it_next = dist.find(next_key);
                if (it_next == dist.end() || next_info < it_next->second) {
                    // If this path is better or if the neighbor state hasn't been reached before,
                    // update the distance map and push the new state into the priority queue.
                    dist[next_key] = next_info;
                    pq.push({next_info, next_key});
                }
            }
        }

        // Explore Rewind action if the current square (r, c) is a mysterious square
        if (mysterious_squares.count({r, c})) {
            // Check if we are within the limit for the number of rewinds 'k'.
            if (k + 1 <= max_k) {
                 // Retrieve the rewind parameters C (time rewind amount) and D (fatigue cost) for this square.
                 pair<ll, ll> rewind_params = mysterious_squares.at({r, c});
                 ll C = rewind_params.first;
                 ll D = rewind_params.second;

                 // Calculate the state after rewind:
                 // Fatigue increases by D.
                 // Time changes by (1 - C). This accounts for the time rewind by C and the 1 second wait period.
                 StateInfo next_info = {f + D, t + (1 - C)};
                 // The number of rewinds increases by 1. The location (r, c) remains the same.
                 StateKey next_key = {k + 1, {r, c}}; 

                 // Check if this path to state {k+1, r, c} is better than any path found so far.
                 auto it_next = dist.find(next_key);
                 if (it_next == dist.end() || next_info < it_next->second) {
                     // If better or first time reaching, update distance map and push state to PQ.
                     dist[next_key] = next_info;
                     pq.push({next_info, next_key});
                 }
            }
        }
    }

    // After Dijkstra's algorithm finishes, examine all reachable states corresponding to the goal square (N, M)
    // for all possible number of rewinds k from 0 to max_k.
    for (int k = 0; k <= max_k; ++k) {
         StateKey goal_key = {k, {N, M}};
         auto it = dist.find(goal_key);
         // Check if the state {k, N, M} was reachable
         if (it != dist.end()) { 
             StateInfo goal_info = it->second; // Get the {fatigue, time} for this state
             // Check if the time 'goal_info.second' meets the time limit T_limit
             if (goal_info.second <= T_limit) { 
                 // If it does, update the overall minimum fatigue found.
                 min_fatigue_at_goal = min(min_fatigue_at_goal, goal_info.first);
             }
         }
     }

    // Output the final result.
    if (min_fatigue_at_goal == INF) {
        // If min_fatigue_at_goal is still INF, it means the goal was not reachable within the time limit.
        cout << -1 << endl;
    } else {
        // Otherwise, output the minimum fatigue found.
        cout << min_fatigue_at_goal << endl;
    }

    return 0; // Indicate successful execution
}