Drafts and rabbits#3214
King Rabbit is a strong and fair ruler. Year after year, he keeps the country at a high level of development, protecting it from attacks by kangaroids and hamstars. The citizens of the kingdom love their King. Spring has arrived, and the King has returned from another campaign.
The King loves spring and asks for as many windows as possible to be opened in the main corridor of his castle. This is not easy, since there are many windows in the castle. Rabbit-servants do not want the King to catch a cold, so they must open the windows in a way that avoids a draft in the corridor.
The corridor can be imagined as two parallel walls with windows. Each window is specified by two coordinates: the start and the end. The walls both start at coordinate and have a length of . The first wall has N_1 windows (the windows do not overlap but may touch), and the second wall has N_2 windows.
A draft happens if there is a straight path for wind through the corridor (the wind blows perpendicular to the walls). Specifically, if two windows are open: on the first wall and on the second, there will be a draft over the interval . For windows and , and even for and , there is no draft.
What is the maximum number of windows that can be opened?
The first line contains three integers separated by spaces: L, N_1, N_2 (1 \leq L \leq 100000, 0 \leq N_1, N_2 \leq L). The next N_1 lines each contain two integers separated by a space, representing the start and end coordinates of a window on the first wall: (0 \leq b < e \leq L). The following N_2 lines, in the same format, describe the windows on the second wall.
Print a single integer: the maximum number of windows that can be opened so that the King does not catch a cold.
Example 1