Large Screen

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.

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.

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