Library Carpet

A rectangular library floor contains several rectangular stains. The stains do not overlap, although they may touch, and every side of every stain is parallel to a wall of the library.

You have one new square carpet. The carpet must be placed parallel to the walls and must lie completely inside the library. A stain is counted as covered only when the whole stained rectangle is contained inside the carpet.

Choose the carpet position that covers as many stains as possible, and compute that maximum number.

All rectangle coordinates are nonnegative integers less than 1,000,000, and every width and height is a positive integer less than 1,000,000. Stain rectangles do not overlap, but they may touch. Every stain rectangle and every valid carpet placement is completely contained in the library rectangle. The number of stain rectangles is at most 100,000.

The first line contains the coordinates of the upper-left and lower-right corners of the library rectangle.

The second line contains the side length of the square carpet.

The third line contains the number of stains.

Each of the following lines contains the coordinates of the upper-left and lower-right corners of one stain rectangle.

Print the maximum number of stains that can be completely covered by one square carpet.