from bisect import bisect_left, bisect_right
import heapq

def main():
    N, M, K, T = map(int, input().split())
    mysterious = {}
    for _ in range(K):
        A, B, C, D = map(int, input().split())
        mysterious[(A-1, B-1)] = (C, D)  # Convert to 0-based indices

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    visited = {}
    for i in range(N):
        for j in range(M):
            visited[(i, j)] = []
    start_i, start_j = 0, 0
    end_i, end_j = N-1, M-1

    heap = []
    heapq.heappush(heap, (0, 0, start_i, start_j))

    def is_dominated(entries, t, f):
        n = len(entries)
        if n == 0:
            return False
        idx = bisect_right(entries, (t, float('inf'))) - 1
        if idx >= 0:
            t_prime, f_prime = entries[idx]
            if t_prime <= t and f_prime <= f:
                return True
        return False

    def add_entry(entries, t, f):
        if is_dominated(entries, t, f):
            return False
        idx = bisect_left(entries, (t, f))
        entries.insert(idx, (t, f))
        i = idx + 1
        while i < len(entries):
            if entries[i][1] >= f:
                del entries[i]
            else:
                i += 1
        return True

    if add_entry(visited[(start_i, start_j)], 0, 0):
        pass

    found = False
    answer = -1

    while heap:
        f, t, i, j = heapq.heappop(heap)
        if i == end_i and j == end_j:
            answer = f
            found = True
            break
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M:
                new_time = t + 1
                new_f = f
                if new_time > T:
                    continue
                entries = visited[(ni, nj)]
                if not is_dominated(entries, new_time, new_f):
                    if add_entry(entries, new_time, new_f):
                        heapq.heappush(heap, (new_f, new_time, ni, nj))
        if (i, j) in mysterious:
            C, D = mysterious[(i, j)]
            new_time = t + 1 - C
            new_f = f + D
            if new_time > T:
                continue
            entries = visited[(i, j)]
            if not is_dominated(entries, new_time, new_f):
                if add_entry(entries, new_time, new_f):
                    heapq.heappush(heap, (new_f, new_time, i, j))

    print(answer if found else -1)

if __name__ == "__main__":
    main()