#include <iostream>
#include <vector>
using namespace std;
using lint = long long;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, M, K, T;
    cin >> N >> M >> K >> T;
    const int req_red = (N - 1) + (M - 1) - T;

    if (T >= (N - 1) + (M - 1)) {
        puts("0");
        return 0;
    }

    vector<int> C(N * M);
    vector<int> D(N * M);

    auto fij = [&](int i, int j) { return i * M + j; };
    auto f = [&](int i, int j, int t) { return (i * M + j) * (req_red + 1) + t; };

    REP(k, K) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --b;
        C.at(fij(a, b)) = c - 1;
        D.at(fij(a, b)) = d;
    }


    const int sz = N * M * (req_red + 1);
    constexpr lint inf = 1LL << 60;
    vector<lint> dp(sz, inf);
    dp.at(f(0, 0, 0)) = 0;

    REP(t, req_red + 1) {
        REP(i, N - 1) REP(j, M) chmin(dp.at(f(i + 1, j, t)), dp.at(f(i, j, t)) + 0);
        REP(i, N) REP(j, M - 1) chmin(dp.at(f(i, j + 1, t)), dp.at(f(i, j, t)) + 0);
        IFOR(i, 1, N) IREP(j, M) chmin(dp.at(f(i - 1, j, t)), dp.at(f(i, j, t)) + 1);
        IREP(i, N) IFOR(j, 1, M) chmin(dp.at(f(i, j - 1, t)), dp.at(f(i, j, t)) + 1);

        REP(i, N) REP(j, M) {
            if (C.at(fij(i, j)) > 0) chmin(dp.at(f(i, j, min(t + C.at(fij(i, j)), req_red))), dp.at(f(i, j, t)) + D.at(fij(i, j)));
        }
    }

    lint ret = dp.at(f(N - 1, M - 1, req_red));
    cout << (ret < inf ? ret : -1) << endl;
}