아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

구슬

시간 제한1초메모리 제한256 MB

요약
빨간색, 파란색, 초록색 구슬을 각각 담는 서로 겹치지 않는 축에 평행한 직사각형 세 개로 구슬 수 합을 최대로 합니다.
난이도

어려움10점 중 8점

유형
기하, 누적 합, 완전 탐색
정답자
아직 제출이 없습니다

문제

세 아이 A, B, C가 구슬 놀이를 한다. 구슬의 색은 빨강, 파랑, 초록 중 하나이고, 놀이를 시작할 때 구슬을 땅에 뿌려 흩어 놓는다. 어떤 두 구슬도 xx좌표가 같지 않고, yy좌표가 같은 두 구슬도 없다.

A, B, C는 각각 땅 위에 직사각형 영역을 하나씩 그린다. 직사각형의 변은 좌표축과 평행하고, 경계를 포함하는 닫힌 영역이다. 세 직사각형은 어느 두 개도 점 하나조차 공유하지 않아야 한다. 직사각형을 한 점으로 줄여서 그려도 된다.

그다음 A는 자기 영역 안에 있는 빨간 구슬만, B는 파란 구슬만, C는 초록 구슬만 센다. 한 개도 세지 못하는 아이가 있어도 된다. 놀이의 목표는 세 아이가 센 구슬 개수의 합을 가장 크게 만드는 것이다.

세 아이가 셀 수 있는 구슬 개수의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다.

각 테스트 케이스의 첫째 줄에는 빨간 구슬, 파란 구슬, 초록 구슬의 개수를 나타내는 세 정수 aa, bb, cc (1≤a,b,c≤100001 \le a, b, c \le 10000)가 주어진다. 이어지는 aa개의 줄에는 빨간 구슬의 좌표 xix_i와 yiy_i가 한 줄에 하나씩 주어진다. 그다음 bb개의 줄에는 파란 구슬의 좌표가, 그다음 cc개의 줄에는 초록 구슬의 좌표가 같은 형식으로 주어진다. 모든 좌표는 0≤xi,yi≤1070 \le x_i, y_i \le 10^7을 만족한다.

한 테스트 케이스 안에서 같은 가로선 위에 놓인 구슬은 많아야 한 개이고, 같은 세로선 위에 놓인 구슬도 많아야 한 개이다.

출력

각 테스트 케이스마다 세 아이가 센 구슬 개수의 합의 최댓값을 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    2
    2 2 1
    1 1
    4 4
    2 2
    5 5
    3 3
    3 4 2
    10 2
    15 9
    14 10
    12 1
    4 5
    2 15
    6 12
    5 8
    3 3
    
    예상 출력
    3
    7
    
  2. 예제 2

    입력
    1
    1 1 1
    0 0
    1 1
    2 2
    
    예상 출력
    3
    
  3. 예제 3

    입력
    2
    3 3 3
    4 1
    12 16
    1 6
    15 0
    13 17
    8 15
    14 12
    5 13
    9 3
    4 4 4
    6 5
    15 23
    5 4
    13 0
    10 21
    2 18
    12 14
    14 19
    17 15
    11 10
    1 22
    16 2
    
    예상 출력
    7
    9