가장 빠른 격자 경로

어떤 도시는 모든 도로가 가로 또는 세로 방향인 무한한 격자 모양이다. 두 도로가 만나는 지점은 정수 좌표 (x, y)로 나타낸다. 보통은 한 블록을 이동하는 데 10의 시간이 걸리므로, 두 지점 (a, b)와 (c, d) 사이를 최단 거리로 이동하면 |a - c| + |b - d|개의 블록을 지난다.

도시에는 차량 정체가 심한 상가 지역들이 있다. 각 상가 지역은 축에 평행한 직사각형이며, 그 직사각형의 내부에 완전히 놓인 도로 구간을 한 블록 이동하는 데 걸리는 시간이 따로 주어진다. 어떤 구간도 상가 지역 내부에 놓이지 않으면 한 블록 이동 시간은 10이다. 상가 지역을 돌아가는 편이 빠를 때도 있고, 일부 지역을 통과하는 편이 빠를 때도 있다.

아래 그림의 상황에서 일반 도로의 한 블록 이동 시간은 10이고, 네 상가 지역 A, B, C, D의 한 블록 이동 시간은 각각 44, 33, 22, 11이다. 두 지점 (1, 6)과 (15, 3) 사이의 가장 빠른 경로는 표시된 경로이며, 길이는 19이고 총 소요 시간은 192이다. 상가 지역을 전혀 지나지 않는 가장 빠른 경로는 길이가 21이고 총 소요 시간은 210이다.

주어진 두 지점 사이를 이동하는 데 필요한 최소 시간을 구하시오.

첫째 줄에 네 정수 a b c d가 주어진다. (a, b)는 출발 지점, (c, d)는 도착 지점이며 두 지점은 서로 다르다.

둘째 줄에 상가 지역의 수 n이 주어진다. 0 <= n <= 1000이다.

다음 n개의 줄에는 상가 지역 하나를 나타내는 다섯 정수 lx ly hx hy t가 주어진다. (lx, ly)는 직사각형의 왼쪽 아래 꼭짓점, (hx, hy)는 오른쪽 위 꼭짓점이며, 그 내부 도로에서 한 블록을 이동하는 데 걸리는 시간은 t이다. 10 <= t <= 10^8이고, 모든 좌표는 0 이상 10^8 이하의 정수이다. 서로 다른 두 상가 지역은 겹치지 않으며 경계도 닿지 않는다.

출발 지점에서 도착 지점까지 이동하는 데 필요한 최소 시간을 출력한다.