Container transport

The mechanized depot run by the SACA - Store Any Container Anywhere company, is a large rectangular hall. The floor of the hall is divided into squares of equal size by the rectangular grid parallel to the depot walls. The depot is used to store containers of various size. Due to advanced standardization in container industry, the shape of any container is a rectangular cuboid. The lengths of sides of the cuboid base can be expressed as an integer multiple of the so-called container unit length. The size of each square side on the depot floor is exactly one container unit length. Therefore, any container in the depot can be positioned in such way that it fully covers some squares on the floor and it does not cover other squares, even not partially. The automated storage system in the depot relies on this property to move containers around in the depot.

The movement consists of steps. In one step, a container can be moved by one square in any of four directions parallel to the depot walls. A container cannot be rotated during the movement. There are two kind if steps, the fast step and the slow step.
The fast step is applied each time when immediately before the step, or during the step, or immediately after the step, none of the floor squares under the moved container is adjacent either to the wall or to a square on which some other container is currently standing. (Two squares are adjacent when they share an edge or a corner, a square is adjacent to a wall if its side coincides with the wall.)
In all other cases the slow step is applied. The slow step reflects the fact that the container manipulation typically has to be done with greater care when the container is close to the wall or to another container.

The depot system is about to be upgraded to become fully autonomous. A part of the upgraded system will be the module which calculates the fastest sequence of steps which transport a container from its original position to some other target position in the depot.

     


Image 1. Examples of container transport in the depot. The transported container is highlighted in orange. The target position of the container is depicted as empty rectangle with dotted perimeter. The dotted path depicts the shortest path of transport of the container from its original to its target position. Each dot on the path corresponds to the square under the upper left corner of the container. Case a) supposes that the duration of the fast and the slow step is the same, case b) supposes that a slow step is 8 times slower than a fast step. Cases a) and b) illustrate Examples 1 and 2 below.

The task

You are given the layout of the depot and its contents, the original and the target positions of the transported container, and the duration of the fast and the slow step. Determine the minimum time in which the transported container can be moved from its original position to its target position.

Input

The depot is described as a rectangle positioned in the plane, its sides aligned with the axes and one of its corners coincides with axes origin. The first input line contains two integers N, M, the width (along the x-axis) and the height (along the y-axis) of the depot expressed in terms of container unit length.

The second input line contains two integers F, S which represent the duration of the fast step and the slow step, respectively. The third input line contains a single integer K, the number of containers in the depot. Each of the next K lines specify one containers position. The line contains four non-negative integers x1, y1, x2, y2 describing the coordinates [x1, y1] of the square under the bottom left corner of the container and the coordinates [x2, y2] of the square under the top right corner of the container.
The bottom left corner of a container is its corner closest to the axes origin, the top right corner of the square is its corner farthest from the axes origin.
The coordinates of the original position of the transported container are listed before the coordinates of all other containers. The last input line contains the first pair of the target coordinates [x, y] of the transported container.
It holds, 3 ≤ N, M ≤ 100.

Output

The output is one line with a single integer denoting the minimum time in which the container can be transported form its originial position to its target position. If the transport is impossible the line contains value −1.

Example 1

Input
9 7
1 1
3
0 1 2 2
4 2 5 3
1 4 1 5
3 4
Output
14

Example 2

Input
9 6 
1 8 
4
1 2 2 2
3 2 3 2
8 2 8 4
1 0 1 0
4 1
Output
31

Example 3

Input
6 6
1 2
3
0 0 2 2
4 1 4 1
1 4 1 4
3 3
Output
-1

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set