The city of JOI has a well-developed public transport network which consists of several bus routes. The buses travel on the city's bus-only roads, which are laid out in a grid-like fashion. Since these roads are bus-only roads, buses are not affected by traffic conditions and move at a constant speed. There are W roads oriented in the north-south direction, spaced 1 km apart. There are H roads oriented in the east-west direction, spaced 1 km apart. All buses travel in a clockwise fashion on a fixed rectangular route at a speed of 1 km per minute. There are bus stops at every intersection of the grid.
Today, JOI-kun plans to watch a cricket match, but he overslept. Although he might not be able to catch the start of the cricket match, JOI-kun wants to maximize the remaining time he has left at the match, so he wants to get to the cricket arena as fast as possible.
JOI-kun is already familiar with the public transport network. He knows the current position and fixed rectangular route of every bus. Setting out right now, JOI-kun wants to get to the cricket arena as fast as possible through the public transport network. JOI-kun begins at a bus stop and is able to board buses whenever the bus passes by his current bus stop. Boarding a bus takes no time at all and has a negligible effect on the movement of the bus. JOI-kun is also able to alight from buses at any bus stop along the bus's route, which takes no time at all and similarly does not affect the movement of the bus. However, since the buses spend a negligible amount of time at each bus stop, JOI-kun is only able to board the next bus 1 minute after he alights at a bus stop.
It is guaranteed that JOI-kun is able to reach the cricket arena through the public transport network. Find the earliest time that JOI-kun can reach the cricket arena.
Read from standard input.
- On the first line, there are six integers, W, H, SX, SY, GX and GY (1 ≤ SX ≤ W and 1 ≤ SY ≤ H and 1 ≤ GX ≤ W and 1 ≤ GY ≤ H). This means that there are W north-south bus roads spaced 1 km apart and H east-west bus roads spaced 1 km apart. JOI-kun is on the intersection between the SXth bus road from the west and the SYth bus road from the north. The cricket arena is on the intersection between the GXth bus road from the west and the SYth bus road from the north. JOI-kun's location is guaranteed to be different from the cricket arena's position. In addition, at the moment of departure, there is no bus at JOI-kun's location.
- The second line contains 1 integer, N. N represents the number of buses operating in JOI city's public transport network.
- On the ith line of the next N lines, there are 5 integers, X1i, Y1i, X2i, Y2i and Ti (1 ≤ X1i < X2i ≤ W and 1 ≤ Y1i < Y2i ≤ H and 0 ≤ Ti < 2 × (X2i - X1i + Y2i - Y1i)). This means that the ith bus's route is a rectangle defined by its two opposite corners. The north-west corner is the intersection between the X1ith bus road from the west and the Y1ith bus road from the north. The south-east corner is the intersection between the X2ith bus road from the west and the Y2ith bus road from the north. In addition, at JOI-kun's moment of departure, the bus has travelled Ti km in a clockwise fashion from the north-west corner of its route.
Print to standard output a single integer representing the earliest time that JOI-kun can reach the cricket arena.
All test cases satisfy the following constraints.
- 2 ≤ W ≤ 1 000.
- 2 ≤ H ≤ 1 000.
- 1 ≤ N ≤ 1 000.
Subtask 1 (30 points):
The following constraints are satisfied:
Subtask 2 (50 points):
The following constraints are satisfied:
- W ≤ 300.
- H ≤ 300.
- N ≤ 300.
Subtask 3 (20 points):
No further constraints.
Sample Input 1
10 10 1 3 10 1
1 3 5 6 4
5 5 7 10 1
7 1 10 5 9
Sample Output 1
The diagram above represents JOI city from above. Circles represent the initial location of the buses and arrows represent the buses' rectangular route. JOI-kun is located at the triangle and the cricket arena is at the square.
JOI-kun has no choice but to wait for bus 1 to arrive. 10 minutes later, he boards bus 1. The following diagram shows the state of JOI city at 11 minutes.
Following that, JOI-kun must transfer to bus 2. At 16 minutes, JOI-kun alights from bus 1. The following diagram shows the state of JOI city at 19 minutes.
After boarding bus 2, JOI-kun must transfer to bus 3. At 29 minutes, JOI-kun alights from bus 2. At the very point in time JOI-kun alights, bus 3 passes through the same bus stop. However, JOI-kun cannot board bus 3 since he is alighting from bus 2 at the time.
At 43 minutes, JOI-kun boards bus 3. The following diagram shows the state of JOI city at 49 minutes.
One minute later, JOI-kun arrives at the cricket arena. Since this is the earliest time JOI-kun can arrive at the arena, the correct output is 50.
Sample Input 2
4 3 2 1 4 3
1 1 4 2 0
1 1 2 2 3
2 2 4 3 3
Sample Output 2