import sys
input = sys.stdin.readline
from heapq import heappop,heappush

N,M,K,T=map(int,input().split())

X=[[(-1,-1)]*M for i in range(N)]

for i in range(K):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    X[a][b]=[c,d]

DP=[[[1<<63]*M for i in range(N)] for j in range(400)]

Q=[(0,0,0,0)]
DP[200][0][0]=0

while Q:
    #print(Q)
    now,x,y,time=heappop(Q)

    for z,w in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
        if 0<=z<N and 0<=w<M and 0<=time+1+200<400 and DP[time+1+200][z][w]>now:
            DP[time+1+200][z][w]=now
            heappush(Q,(DP[time+1+200][z][w],z,w,time+1))

    if X[x][y]!=(-1,-1):
        c,d=X[x][y]
        if 0<=time-c+200<400 and DP[time-c+200][z][w]>now+d:
            DP[time-c+200][z][w]=now+d
            heappush(Q,(DP[time-c+200][z][w],x,y,time-c))

ANS=1<<63

for i in range(400):
    if i-200<=T:
        ANS=min(ANS,DP[i][N-1][M-1])

print(ANS)