시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Vô Giuseppe ganhou de presente um cortador profissional de pizza, daqueles do tipo carretilha e, para comemorar, assou uma pizza retangular gigante para seus netos! Ele sempre dividiu suas pizzas em pedaços fazendo cortes ao longo de linhas contínuas, não necessariamente retilíneas, de dois tipos: algumas começam na borda esquerda da pizza, seguem monotonicamente para a direita e terminam na borda direita; outras começam na borda inferior, seguem monotonicamente para cima e terminam na borda superior. Mas Vô Giuseppe sempre seguia uma propriedade: dois cortes do mesmo tipo nunca podiam se interceptar. Veja um exemplo com 4 cortes, dois de cada tipo, na parte esquerda da figura, que dividem a pizza em 9 pedaços.

Acontece que Vô Giuseppe simplesmente ama geometria, topologia, combinatória e coisas assim; por isso, resolveu mostrar para as crianças que poderia obter mais pedaços, com o mesmo número de cortes, se cruzamentos de cortes de mesmo tipo fossem permitidos. A parte direita da figura mostra, por exemplo, que se os dois cortes do tipo dos que vão da esquerda para a direita puderem se interceptar, a pizza será dividida em 10 pedaços.

Vô Giuseppe descartou a propriedade, mas não vai fazer cortes aleatórios. Além de serem de um dos dois tipos, eles vão obedecer às seguintes restrições:

  • Dois cortes têm no máximo um ponto de interseção e, se tiverem, é porque os cortes se cruzam naquele ponto;
  • Três cortes não se interceptam num mesmo ponto;
  • Dois cortes não se interceptam na borda da pizza;
  • Um corte não intercepta um canto da pizza.

Dados os pontos de começo e término de cada corte, seu programa deve computar o número de pedaços resultantes dos cortes do Vô Giuseppe.

입력

A primeira linha da entrada contém dois inteiros X e Y , (1 ≤ X, Y ≤ 109), representando as coordenadas (X, Y ) do canto superior direito da pizza. O canto inferior esquerdo tem sempre coordenadas (0, 0). A segunda linha contém dois inteiros H e V , (1 ≤ H, V ≤ 105), indicando, respectivamente, o número de cortes que vão da esquerda para a direita, e o número de cortes que vão de baixo para cima. Cada uma das H linhas seguintes contém dois inteiros Y1 e Y2 definindo as ordenadas de encontro dos lados verticais da pizza com um corte que vai do lado esquerdo, na ordenada Y1, para o lado direito, na ordenada Y2. Cada uma das V linhas seguintes contém dois inteiros X1 e X2 definindo as abscissas de encontro dos lados horizontais da pizza com um corte que vai do lado inferior, na abscissa X1, para o lado superior, na abscissa X2.

출력

Imprima uma linha contendo um inteiro representando o número de pedaços resultantes.

예제 입력 1

3 4
3 2
1 2
2 1
3 3
1 1
2 2

예제 출력 1

13

예제 입력 2

5 5
3 3
2 1
3 2
1 3
3 4
4 3
2 2

예제 출력 2

19

예제 입력 3

10000 10000
1 2
321 3455
10 2347
543 8765

예제 출력 3

6