#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 80 + 5;
const ll LOG = 31;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'

ll n, m, k, t, tt;
pll a [MAXN][MAXN];
ll dis [MAXN][MAXN][4*MAXN];
bool vis [MAXN][MAXN][4*MAXN];
priority_queue <array <ll, 4>, vector <array <ll, 4> > , greater <array <ll, 4> > > pq;
ll ans = INF;

void dijk(){
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            for(ll u = 0; u <= 2*tt; u++){
                dis[i][j][u] = INF;
                vis[i][j][u] = 0;
            }
        }
    }
    dis[1][1][tt] = 0;
    pq.push({0, 1, 1, tt});
    while(!pq.empty()){
        auto nw = pq.top();
        pq.pop();
        if(vis[nw[1]][nw[2]][nw[3]]) continue;
        vis[nw[1]][nw[2]][nw[3]] = 1;
        // cout << nw[0] << " " << nw[1] << " " << nw[2] << " " << nw[3] << endl;
        if(nw[3]+1 <= 2*tt){
            if(nw[1]+1 <= n && nw[0] < dis[nw[1]+1][nw[2]][nw[3]+1]){
                dis[nw[1]+1][nw[2]][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1]+1, nw[2], nw[3]+1});
            }
            if(nw[1]-1 >= 1 && nw[0] < dis[nw[1]-1][nw[2]][nw[3]+1]){
                dis[nw[1]-1][nw[2]][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1]-1, nw[2], nw[3]+1});
            }
            if(nw[2]+1 <= m && nw[0] < dis[nw[1]][nw[2]+1][nw[3]+1]){
                dis[nw[1]][nw[2]+1][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1], nw[2]+1, nw[3]+1});
            }
            if(nw[2]-1 >= 1 && nw[0] < dis[nw[1]][nw[2]-1][nw[3]+1]){
                dis[nw[1]][nw[2]-1][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1], nw[2]-1, nw[3]+1});
            }
        }
        if(a[nw[1]][nw[2]].fi != 0){
            ll c = a[nw[1]][nw[2]].fi, d = a[nw[1]][nw[2]].se;
            ll cnt = max(ll(0), nw[3]-c+1);
            if(nw[0]+d < dis[nw[1]][nw[2]][cnt]){
                dis[nw[1]][nw[2]][cnt] = nw[0]+d;
                pq.push({nw[0]+d, nw[1], nw[2], cnt});
            }
        }
    }
}

void solve(){
    cin >> n >> m >> k >> t;
    tt = n+m-2;
    for(ll i = 1; i <= k; i++){
        ll x, y, v, w; cin >> x >> y >> v >> w;
        a[x][y] = {v, w};
    }
    dijk();
    for(ll i = 0; i <= tt + min(t,tt); i++){
        // cout << i-tt << " " << dis[n][m][i] << endl;
        ans = min(ans, dis[n][m][i]);
    }
    if(ans != INF) cout << ans << endl;
    else cout << -1 << endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // ll t; cin >> t;
    // while(t--){
        solve();
    // }
}