Library

Robinson Crusoe lives alone on a remote island. One day a ship carrying a royal library wrecks nearby. As usual, Robinson salvages anything useful, and this time he brings back a large chest of books.

He decides to build a bookcase for the books. He cuts a rectangular niche in the rock, hammers in wooden pegs, and lays a wooden plank across every pair of pegs that sit at the same height, so that all planks are horizontal and serve as shelves.

Unfortunately, one especially old and large tome does not fit. Robinson measures its height and width and decides to redesign the bookcase so the tome fits completely on one of the shelves, taking into account the other shelves and the size of the niche. For each shelf, exactly one of the following operations may be applied:

1. Leave the shelf where it is.
2. Move the shelf left or right.
3. Shorten the shelf by cutting off part of the plank, and optionally move it left or right.
4. Move one of its pegs to another place at the same height, and move the shelf left or right.
5. Shorten the shelf by cutting off part of the plank, move one of its pegs to another place at the same height, and optionally move the shortened shelf left or right.
6. Remove the shelf together with both of its supporting pegs.

A shelf is properly supported by its pegs if exactly two distinct pegs support it and the center of the shelf lies between the pegs or coincides with one of them. In the original design every shelf is properly supported and every shelf length is an integer number of inches. Robinson can cut off only an integer number of inches, because he has no tools for finer measurement. After the redesign, every remaining shelf must still be properly supported.

Find a redesign that fits the old tome while changing the original design as little as possible. First minimize the number of pegs that must be removed from their original places (operations 4 and 5 remove one peg, operation 6 removes two). Among all such redesigns, minimize the total length of plank that must be cut off (operations 3 and 5 cut off some length, and operation 6 counts as cutting off the whole plank). Treat plank width and peg diameter as zero.

The tome may not be rotated. It must stand completely (across its whole width) on one shelf, and it may only touch other shelves, their pegs, or the edges of the niche.

The first line contains four integers $X_N$, $Y_N$, $X_T$, $Y_T$ — the width and height of the niche and the width and height of the old tome, in inches ($1 \le X_N, Y_N, X_T, Y_T \le 1000$).

The second line contains an integer $N$ ($1 \le N \le 100$) — the number of shelves. Each of the next $N$ lines describes one shelf and its two supporting pegs with five integers $y_i$, $x_i$, $l_i$, $x1_i$, $x2_i$:

• $y_i$ ($0 < y_i < Y_N$) — the height of shelf $i$ above the bottom of the niche.
• $x_i$ ($0 \le x_i < X_N$) — the distance from the left edge of the niche to the left end of shelf $i$.
• $l_i$ ($0 < l_i \le X_N - x_i$) — the length of shelf $i$.
• $x1_i$ ($0 \le x1_i \le l_i/2$) — the distance from the left end of shelf $i$ to its left peg.
• $x2_i$ ($l_i/2 \le x2_i \le l_i$; $x1_i < x2_i$) — the distance from the left end of shelf $i$ to its right peg.

All shelves are at different heights and are properly supported by their pegs. The input is guaranteed to have a solution.

Print two integers separated by a space. The first is the minimum number of pegs Robinson must remove from their original places in order to fit the tome. The second is the minimum total length (in inches) of plank that must be cut off, taken over all redesigns that remove that minimum number of pegs.