Problem: Pipes

Want to try solving this problem? You can submit your code online if you log in or register.

Pipes

Input File: pipesin.txt
Output File: pipesout.txt
Time Limit: 0.6 seconds
Memory Limit: 64 Mb

A real estate developer wishes to connect their new housing estate to the city's water mains, in order to offer running water as one of the exclusive features of this new development. Some discussion with the council's civic planners reveals that this may be more difficult than anticipated.

The city has a network of underground water pipes, arranged in a repeating grid with a spacing of w metres in the east-west direction and h metres in the north-south direction, as illustrated below.

The housing estate must be joined to one of these underground pipes using official council connectors, which come in a number of types. Each type of connector has a particular size, where an a x b connector can either carry water a metres north/south and b metres east/west, or alternatively a metres east/west and b metres north/south. You may use each type of connector as many times as you like, or you may choose not to use it at all.

Your connectors must be joined end-to-end, with the initial connector starting at the housing estate and the final connector ending somewhere on a city pipe. Your connectors may cross the underground pipes and/or each other without interference. You may assume that the grid of city pipes is extremely large, so that no matter how far your connectors run from the housing estate there are still pipes around.

Note that in some cases you might never be able to join the housing estate to the water mains (which will unfortunately lower the value of the housing estate).

Consider the scenario illustrated in the following diagram. Here the grid of underground pipes has spacing w = 8 and h = 4, and the housing estate is placed six metres east and two metres south from a grid corner. Suppose that the available connectors have dimensions 3 x 1 and 7 x 3. The housing estate can be connected to the pipes using two 3 x 1 connectors (and no 7 x 3 connectors) as shown.

Your task is to join the housing estate to some part of an underground pipe using as few official council connectors as possible.

Input

The first line of input will contain two space-separated integers w h, representing the width and height of the grid segments respectively (1 <= w,h <= 500). The second line of input will contain two space-separated integers x y, representing the position of the housing estate within a grid segment (0 <= x <= w, 0 <= y <= h). Here x and y are measured east and south respectively from the top-left corner of the grid segment.

The third line of input will contain a single integer n representing the number of types of connectors available (1 <= n <= 10). The next n lines will each contain two non-negative integers a_i b_i, with the ith of these lines giving the size of the ith type of connector (0 <= a_i,b_i <= 500).

Output

The output should contain a single integer m giving the minimum number of official council connectors needed to join the housing estate to the underground pipes, if this is possible. If it is not possible, you should output the single word "No".

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

No

Scoring

The score for each input file will be 100% if a correct answer is written to the output file, and 0% otherwise.