The Hottest Piece of Cheese
Time limit1sMemory limit512 MB
Given two families of non-crossing cuts across a rectangle and points inside it, find the piece containing the most peppers.
- Level
Medium7 of 10
- Topics
- Geometry, Sorting, Prefix sum
- Solved
- No attempts yet
Problem
Mirko has a two dimensional cheese of width and height . He makes cuts of type A, each of which crosses both the left edge and the right edge of the cheese. Then he makes cuts of type B, each of which crosses both the top edge and the bottom edge. Two cuts of the same type never meet. Inside the cheese there are hot peppers, each given by its and coordinates. After the cheese is cut, Mirko wants to know how many peppers the hottest piece holds. Help Mirko.

Input
The first line contains the width and the height of the cheese (, ).
The second line contains the number of peppers (). Each of the next lines contains two integers and , the coordinates of one pepper (, ). No pepper lies on a cut, and no two peppers share the same coordinates.
The next line contains the number of cuts that cross both the left edge and the right edge (). Each of the next lines contains two integers and , the coordinates where that cut meets the left edge and the right edge (, ).
The next line contains the number of cuts that cross both the top edge and the bottom edge (). Each of the next lines contains two integers and , the coordinates where that cut meets the top edge and the bottom edge (, ).
No two cuts that cross the left and the right edge intersect or touch each other. The same holds for the cuts that cross the top and the bottom edge.
The coordinates follow the standard Cartesian system. grows from left to right and grows from bottom to top.
Output
Print one line with the number of peppers in the piece that contains the most peppers.