#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 REP(i, n) FOR(i,0,n)
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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) REP(j, M) {
            for (auto [di, dj] : grid_dxs) {
                int ni = i + di, nj = j + dj;
                if (ni < 0 or ni >= N or nj < 0 or nj >= M) continue;
                chmin(dp.at(f(ni, nj, t)), dp.at(f(i, j, t)));
            }
        }
        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;
}