import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd

n,m,k,t = map(int,input().split())
t = min(t, 500)
wonderc = defaultdict()
wonderd = defaultdict()
for i in range(k):
    a,b,c,d = map(int,input().split())
    wonderc[(a,b)] = c
    wonderd[(a,b)] = d
#ダイクストラ法
def dijkstra(s): # sがスタート、nが頂点数
    INF = 10**15
    dist = [[INF]*(1000) for i in range(n*m)]
    que = [(0,s,500)]
    dist[s][500] = 0
    while que:
        c,crr,tt = heappop(que)
        x,y = crr//m, crr%m
        # print(x,y,tt)
        if c > dist[crr][tt]: continue
        if (x,y) in wonderc.keys():
            if dist[crr][max(0, tt-wonderc[(x,y)]+1)] > dist[crr][tt]+wonderd[(x,y)]:
                dist[crr][max(0, tt-wonderc[(x,y)]+1)] = dist[crr][tt]+wonderd[(x,y)]
                heappush(que,(dist[crr][max(0, tt-wonderc[(x,y)]+1)],crr, max(0, tt-wonderc[(x,y)]+1)))
        for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx,ny = x+dx,y+dy
            if not(0<=nx<n and 0<= ny<m): continue
            nxt = nx*m + ny
            if dist[crr][tt] < dist[nxt][min(1000-1,tt+1)]:
                dist[nxt][min(1000-1,tt+1)] = dist[crr][tt]
                heappush(que,(dist[nxt][min(1000-1,tt+1)],nxt,min(1000-1,tt+1)))
    return dist

d =dijkstra(0)
print(min(d[-1][:t+500]))