Problem L
Taxi Driver

Image by Ryjkov_S (Shutterstock); Used under license

Travis has been a taxi driver in the city of Kroywen for many years. He used to like his job, but the steady increase in traffic over the decades has produced a corresponding increase in his level of stress. Now the only part of the workday he enjoys is hanging out with his fellow drivers at the diner near the taxi stand where they wait for calls. Other than making enough money to get by, Travis’s primary objective when working is to maximize the amount of time he can spend at the diner.

Kroywen is laid out as an east-west/north-south grid. The streets run east-west and the avenues run north-south. Streets are numbered $1, 2, \ldots , N$ from north to south, and avenues are numbered $1, 2, \ldots , M$ from west to east. An intersection is specified as an ordered pair $(s,a)$, where $s$ is a street number and $a$ is an avenue number. The taxi stand is located at $(1,1)$.

It takes Travis exactly $1$ minute to drive the length of a city block, i.e., from any intersection to the intersection immediately north, south, east, or west (all streets and avenues are bi-directional). This is not particularly frustrating, but what is frustrating is the time required to navigate intersections. If an intersection is not undergoing construction, it takes $1$ minute to drive straight through, $2$ minutes to turn right, and $3$ minutes to turn left (no U-turns allowed). If an intersection is undergoing construction, these times may vary significantly.

When Travis gets a call, he leaves the taxi stand, drives to the pickup location, drives from there to the dropoff location, and then returns to the taxi stand. Pickup and dropoff locations are always intersections, and it takes a customer a negligible amount of time to get in or out of the taxi. Travis wants your help to minimize the number of minutes needed for such a trip by choosing his route carefully.

Note that Travis can leave the taxi stand driving either east or south, and he can return to the taxi stand driving west or north. Every other intersection he passes through (possibly turning right or left) incurs the corresponding time penalty, but no additional time is required to depart from, enter, or pass through $(1,1)$. (It’s possible that Travis will need to pass through $(1,1)$ on his way from the pickup location to the dropoff location. This may seem strange, but not much surprises Travis anymore.)

Input

The first line of input contains three space-separated integers, $N$, $M$, $C$, where $N$ is the number of streets, $M$ is the number of avenues $(2 \leq N, M \leq 100)$, and $C$ is the number of intersections undergoing construction $(0 \leq C < N \cdot M)$. The second line contains four space-separated integers, $s_ p$, $a_ p$, $s_ d$, $a_ d$, where $(s_ p, a_ p)$ is the pickup intersection and $(s_ d, a_ d)$ is the dropoff intersection. Street numbers $s_ p, s_ d$ are in the interval $[1,N]$, and avenue numbers $a_ p, a_ d$ are in the interval $[1,M]$. The pickup and dropoff intersections are distinct, and neither is equal to $(1,1)$. This is followed by $C$ lines, each of which gives delay information for an intersection undergoing construction in the form of five space-separated integers, $s, a, t, r, \ell $, where $(s,a)$ is the intersection, $t$ is the time required to drive straight through, $r$ is the time required to turn right, and $\ell $ is the time required to turn left $(0 \leq t, r, \ell \leq 10)$ (all times in minutes). The $C$ intersections are distinct, and $(1,1)$ is never undergoing construction.

Output

Output a single integer: the minimum number of minutes needed for Travis to depart the taxi stand, drive to the pickup location, drive from there to the dropoff location, and then return to the taxi stand.

6 8 0
3 7 5 5

42

6 8 1
3 7 5 5
4 7 10 10 10

45