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: now,x,y,time=heappop(Q) if DP[time+200][x][y]!=now: continue for z,w in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]: if 0<=znow: 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+1+200<400 and DP[time-c+1+200][x][y]>now+d: DP[time-c+1+200][x][y]=now+d heappush(Q,(DP[time-c+1+200][x][y],x,y,time-c+1)) elif time-c+1+200<0 and DP[0][x][y]>now+d: DP[0][x][y]=now+d heappush(Q,(DP[0][x][y],x,y,-200)) ANS=1<<63 for i in range(400): if i-200<=T: ANS=min(ANS,DP[i][N-1][M-1]) if ANS>=1<<60: print(-1) else: print(ANS)