A Brief Gerrymander

Interview

Time limit1sMemory limit128 MB

Summary

Choose A avenue boundaries including 1 and 100 to maximize the number of vertical strips that contain at least one marked neighborhood, given fixed street boundaries.

Level: Hard8 of 10
Topics: Dynamic programming, Sorting, Greedy
Solved: No attempts yet

Problem

The ruling party is redrawing your city's electoral regions (ridings) and is trying to pack certain opposition-friendly neighborhoods into as few ridings as possible. As a member of the opposition, you must arrange the districts so that opposition-friendly neighborhoods are spread across as many ridings as possible.

The city is a grid formed by streets and avenues. Streets run north-south and avenues run east-west; both are numbered starting from the southwest corner of the city. Four roads on the outer edge are always district boundaries: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), and 100th Avenue (north edge).

Districts are formed by choosing some streets as north-south boundaries and some avenues as east-west boundaries. The ruling party has already fixed the street (north-south) boundaries, but you get to choose the avenue (east-west) boundaries. Each riding is one rectangle bounded by two adjacent street boundaries and two adjacent avenue boundaries.

A neighborhood is exactly one block: the cell between two adjacent streets and two adjacent avenues. It is identified by the street and avenue number of its southwest corner. For example, the neighborhood whose southwest corner is at street $47$ , avenue $67$ lies between 47th and 48th Street and between 67th and 68th Avenue.

You must place exactly $A$ avenue boundaries, which always include 1st Avenue and 100th Avenue. Choose them so that the number of ridings containing at least one opposition-friendly neighborhood is as large as possible.

Input

The input contains several test cases, each describing one city.

The first line contains $N$ , the number of opposition-friendly neighborhoods.
Each of the next $N$ lines contains two integers: the street number and the avenue number of the southwest corner of one neighborhood.
The next line contains $S$ followed by the $S$ street numbers used as north-south boundaries, given in increasing order.
The final line contains $A$ (with $A \ge 2$ ), the number of avenue (east-west) boundaries you must place.

The input ends with a line containing a single $-1$ . All street and avenue numbers are between 1 and 100.

Output

For each test case, output a single line containing one integer: the maximum possible number of ridings that contain at least one opposition-friendly neighborhood, taken over all valid placements of the $A$ avenue boundaries.

Examples2

Example 1
Input
```
2
49 49 
50 50
2 1 100
3
-1
```
Expected output
```
2
```
Example 2
Input
```
1
10 20
2 1 100
2
-1
```
Expected output
```
1
```