cho.sh

육아 당번 나누기 (Large)

고정된 활동 시간을 피하면서 두 사람이 하루 720분씩 아기 돌보기를 맡고, 교대 횟수를 최소로 하는 분할을 찾는다.

보통7그리디동적 계획법정렬구현아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

카메론과 제이미는 오랜 인생 동반자이고, 얼마 전 부모가 되었다. 아이를 돌보는 일은 즐겁지만 쉽지만은 않다. 두 사람 모두 과학적으로 사고하는 편이라 육아도 과학적으로 하기로 했다.

두 사람은 하루 일과를 정리하면서 각 시간대에 누가 아이를 맡을지 정하려고 한다. 지금까지 모든 일을 똑같이 나눠 왔고 앞으로도 그러고 싶으므로, 각자 하루에 정확히 12시간(720분)씩 아이를 맡기로 했다.

두 사람에게는 각자 혼자 해야 하는 일정이 있다. 카메론의 일정은 ACA_C개, 제이미의 일정은 AJA_J개이고, 매일 같은 시각에 반복된다. 카메론의 일정과 제이미의 일정은 서로 겹치지 않으므로 언제나 적어도 한 사람은 아이를 맡을 수 있다.

두 사람이 원하는 하루 당번표의 조건은 다음과 같다.

  • 육아 당번 시간은 자신의 일정과 겹치면 안 된다. 즉 카메론의 일정 시간에는 제이미가, 제이미의 일정 시간에는 카메론이 아이를 맡는다.
  • 카메론과 제이미에게 배정된 육아 시간은 각각 정확히 720분이다.
  • 교대 횟수, 즉 아이를 맡는 사람이 바뀌는 횟수가 최소여야 한다.

예를 들어 제이미에게 오전 9시부터 10시까지 일정이 하나, 카메론에게 오후 2시부터 3시까지 일정이 하나 있다고 하자. 제이미가 자정부터 오전 6시까지와 정오부터 오후 6시까지 아이를 맡고 카메론이 나머지 시간을 맡으면 앞의 두 조건은 만족한다. 그러나 교대가 자정, 오전 6시, 정오, 오후 6시에 일어나 모두 4번이다. 자정에 교대가 일어나면 0번이나 2번이 아니라 정확히 1번으로 센다. 카메론이 자정부터 정오까지, 제이미가 정오부터 자정까지 맡으면 같은 두 조건을 만족하면서 교대가 2번뿐이고, 이보다 줄일 수는 없다.

카메론과 제이미의 일정이 주어질 때, 하루 당번표에서 가능한 교대 횟수의 최솟값을 구하라.

입력

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

각 테스트 케이스의 첫 줄에는 카메론의 일정 수 ACA_C와 제이미의 일정 수 AJA_J가 공백으로 구분되어 주어진다. 다음 AC+AJA_C + A_J개의 줄 중 앞의 ACA_C개 줄에는 카메론의 ii번째 일정을 나타내는 두 정수 CiC_i와 DiD_i가 주어진다. 이 일정은 자정으로부터 CiC_i분 뒤에 시작해 DiD_i분 뒤에 끝나고, 길이는 Di−CiD_i - C_i분이다. 뒤의 AJA_J개 줄에는 같은 형식으로 제이미의 일정을 나타내는 두 정수 JiJ_i와 KiK_i가 주어진다. 어떤 일정도 하루를 넘기지 않는다. 한 일정이 끝나는 순간에 다른 일정이 시작할 수는 있고, 그 순간에도 교대는 일어날 수 있다.

제한

  • 1≤T≤1001 \le T \le 100
  • 모든 ii에 대해 0≤Ci<Di≤24×600 \le C_i < D_i \le 24 \times 60
  • 모든 ii에 대해 0≤Ji<Ki≤24×600 \le J_i < K_i \le 24 \times 60
  • 모든 구간 [Ci,Di)[C_i, D_i)와 모든 구간 [Ji,Ki)[J_i, K_i)를 모두 모았을 때, 어느 두 구간도 공통 부분이 없다. 구간은 왼쪽이 닫히고 오른쪽이 열려 있으므로 바로 이어지는 두 일정은 사이에 빈 시간이 없으면서도 겹치지 않는다.
  • ∑i(Di−Ci)≤720\sum_i (D_i - C_i) \le 720
  • ∑i(Ki−Ji)≤720\sum_i (K_i - J_i) \le 720
  • 0≤AC≤1000 \le A_C \le 100
  • 0≤AJ≤1000 \le A_J \le 100
  • 1≤AC+AJ≤2001 \le A_C + A_J \le 200

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 교대 횟수의 최솟값이다.

힌트

예제의 첫 번째 케이스에서는 제이미가 자정부터 정오까지, 카메론이 정오부터 자정까지 아이를 맡으면 교대가 2번이다.

두 번째 케이스에서는 카메론의 두 일정 동안 제이미가 아이를 맡아야 하는데 그 두 구간의 길이 합이 720분이라 제이미의 시간이 모두 채워진다. 남은 시간은 전부 카메론이 맡고, 교대는 4번이다.

세 번째 케이스에서는 자정 직전에 제이미가, 직후에 카메론이 아이를 맡으므로 자정에 교대가 한 번 일어난다. 남은 1438분을 어떻게 나누어도 반대 방향 교대가 적어도 한 번 더 필요하고, 그보다 많이 만들 이유는 없으므로 답은 2이다.

네 번째 케이스처럼 같은 사람의 일정끼리도, 다른 사람의 일정끼리도 바로 이어질 수 있다. 자정 직전과 직후가 모두 카메론의 일정이라 자정에는 교대가 없다. 대신 2분부터 1438분까지의 빈 시간 안에 제이미가 맡는 718분짜리 구간을 통째로 넣어야 하므로 교대는 모두 4번이다. 이 구간을 어디에 두어도 교대 횟수는 같아서 최적 당번표는 여러 가지다.

다섯 번째 케이스에서는 카메론이 100분부터 200분, 500분부터 620분, 900분부터 1400분 구간을 맡는 당번표가 최적이고, 교대는 6번이다.