Large Screen

Time limit1sMemory limit128 MB

Summary

Given a target resolution and physical size, pick a monitor type and orientation and find the minimum-cost grid multiple that meets both requirements.

Level: Medium4 of 10
Topics: Brute force, Math, Implementation
Solved: No attempts yet

Problem

Sanggeun builds a single large monitor by joining several small monitors together in a grid.

A customer specifies the desired large monitor's horizontal and vertical resolution (in pixels) and its horizontal and vertical size (in millimeters). Sanggeun must build a large monitor whose horizontal and vertical resolution are both at least the requested values, and whose horizontal and vertical size are also both at least the requested values. He wants to minimize the manufacturing cost.

A single large monitor must be built from copies of exactly one type of monitor. If the small monitors are arranged in an $a \times b$ grid ( $a$ across and $b$ down), then the large monitor's horizontal resolution and horizontal size are each multiplied by the number placed across, and its vertical resolution and vertical size are each multiplied by the number placed down. The cost equals the total price of the monitors used, that is (number of monitors) $\times$ (price of one monitor).

The warehouse holds several types of monitors, and the resolution, size, and price of each type are known. A monitor may be rotated 90 degrees, which swaps its horizontal and vertical dimensions; however, all monitors inside one large monitor must have the same orientation. Each type of monitor may be used as many times as needed.

Find the minimum possible manufacturing cost.

Input

The first line contains four integers $r_h$ , $r_v$ , $s_h$ , $s_v$ — the large monitor's horizontal resolution, vertical resolution, horizontal size, and vertical size. Each value is between $100$ and $10{,}000$ inclusive.

The second line contains the number of monitor types $n$ ( $1 \le n \le 100$ ).

Each of the next $n$ lines contains five integers $r_{h,i}$ , $r_{v,i}$ , $s_{h,i}$ , $s_{v,i}$ , $p_i$ — a monitor type's horizontal resolution, vertical resolution, horizontal size, vertical size, and price. These values are all between $100$ and $10{,}000$ inclusive.

Output

Print the minimum manufacturing cost of the large monitor on the first line.

Examples7

Example 1

Input

1024 1024 300 300
3
1024 768 295 270 200
1280 1024 365 301 250
1280 800 350 270 210

Expected output

Example 2

Input

100 100 100 100
1
100 100 100 100 500

Expected output

Example 3

Input

400 400 400 400
1
100 100 100 100 100

Expected output

Example 4

Input

1000 100 1000 100
1
100 1000 100 1000 100

Expected output

Example 5

Input

10000 10000 10000 10000
1
100 100 100 100 100

Expected output

Example 6

Input

100 100 10000 10000
1
10000 10000 100 100 100

Expected output

Example 7

Input

500 500 500 500
3
250 250 250 250 100
500 500 500 500 350
300 300 300 300 120

Expected output