#include using namespace std; typedef long long ll; #define int ll typedef pair pii; #define fi first #define se second #define pb push_back const int MOD = 1e9 + 7; const int MAX = 80 + 5; bool vis[MAX][MAX][5*MAX]; ll dist[MAX][MAX][5*MAX]; pii a[MAX][MAX]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k, t; cin >> n >> m >> k >> t; ll tot_time = n - 1 + m - 1; priority_queue , vector>, greater >> pq; for(int i = 0 ; i <= n ; i++){ for(int j = 0 ; j <= m ; j++){ for(int l = 0 ; l <= 2*tot_time ; l++){ dist[i][j][l] = (int)1e15; vis[i][j][l] = 0; a[i][j] = {0, 0}; } } } for(int i = 1 ; i <= k ; i++){ int x, y, v, w; cin >> x >> y >> v >> w; a[x][y] = {v, w}; } dist[1][1][tot_time] = 0; pq.push({0, 1, 1, tot_time}); while(pq.size()){ auto [dis, x, y, tm] = pq.top();pq.pop(); if(vis[x][y][tm])continue; vis[x][y][tm] =1; if(tm + 1 <= 2*tot_time){ if(x + 1 <= n && dis < dist[x + 1][y][tm + 1]){ dist[x + 1][y][tm + 1] = dis; pq.push({dis, x + 1, y, tm + 1}); } if(x - 1 >= 1 && dis < dist[x - 1][y][tm + 1]){ dist[x - 1][y][tm + 1] = dis; pq.push({dis, x - 1, y, tm + 1}); } if(y + 1 <= m && dis < dist[x][y + 1][tm + 1]){ dist[x][y + 1][tm + 1] = dis; pq.push({dis, x, y + 1, tm + 1}); } if(y - 1 >= 1 && dis < dist[x][y - 1][tm + 1]){ dist[x][y - 1][tm + 1] = dis; pq.push({dis, x, y - 1, tm + 1}); } } if(a[x][y].fi != 0){ ll f = a[x][y].fi; ll s = a[x][y].se; ll cnt = max(0ll, tm - f + 1); if(dis + s < dist[x][y][cnt]){ dist[x][y][cnt] = dis + s; pq.push({dis + s, x, y, cnt}); } } } ll ans = (int)1e15; for(int i = 0 ; i <= tot_time + min(t, tot_time) ; i++)ans = min(ans, dist[n][m][i]); cout << (ans == (ll)1e15 ? -1 : ans) << endl; return 0; }