간단한 게리맨더링

집권당이 도시의 선거구(riding)를 다시 나누면서, 야당 성향이 강한 특정 동네들을 되도록 적은 수의 선거구에 몰아넣으려 하고 있다. 당신은 야당의 일원으로서, 야당 성향 동네들이 되도록 많은 선거구에 걸쳐 흩어지도록 구역을 배치해야 한다.

도시는 도로(street)와 대로(avenue)가 이루는 격자다. 도로는 남북 방향으로, 대로는 동서 방향으로 뻗어 있으며, 둘 다 도시의 남서쪽 모서리에서부터 번호가 매겨진다. 도시 바깥 경계를 이루는 네 도로는 항상 선거구 경계가 된다: 1번 도로(서쪽 끝), 100번 도로(동쪽 끝), 1번 대로(남쪽 끝), 100번 대로(북쪽 끝).

선거구는 일부 도로를 남북 경계로, 일부 대로를 동서 경계로 골라서 만든다. 집권당은 이미 도로(남북) 경계를 고정해 두었고, 당신은 대로(동서) 경계를 고를 수 있다. 각 선거구는 이웃한 두 도로 경계와 이웃한 두 대로 경계로 둘러싸인 하나의 직사각형이다.

동네는 정확히 한 블록, 즉 이웃한 두 도로와 이웃한 두 대로 사이의 한 칸이다. 각 동네는 그 남서쪽 모서리의 도로 번호와 대로 번호로 나타낸다. 예를 들어 남서쪽 모서리가 도로 $47$, 대로 $67$인 동네는 47번과 48번 도로 사이, 67번과 68번 대로 사이에 있다.

당신은 정확히 $A$개의 대로 경계를 놓아야 하며, 이 경계에는 항상 1번 대로와 100번 대로가 포함된다. 야당 성향 동네를 하나 이상 포함하는 선거구의 수가 최대가 되도록 대로 경계를 골라라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 하나의 도시를 설명한다.

• 첫 줄에는 야당 성향 동네의 수 $N$이 주어진다.
• 이어지는 $N$개의 줄에는 각 동네의 남서쪽 모서리의 도로 번호와 대로 번호가 두 정수로 주어진다.
• 그다음 줄에는 남북 경계로 쓰이는 도로의 개수 $S$와, 그 $S$개의 도로 번호가 오름차순으로 주어진다.
• 마지막 줄에는 당신이 놓아야 하는 대로(동서) 경계의 개수 $A$($A \ge 2$)가 주어진다.

입력은 $-1$ 하나만 있는 줄로 끝난다. 모든 도로 번호와 대로 번호는 1 이상 100 이하이다.

각 테스트 케이스마다, $A$개의 대로 경계를 놓는 모든 방법 중에서 야당 성향 동네를 하나 이상 포함하는 선거구의 최대 개수를 한 줄에 정수 하나로 출력하라.