육아 분담

Cameron과 Jamie는 오랜 인생의 동반자이며 최근 부모가 되었다! 아기를 돌보는 일은 신나는 만큼 어려움도 따른다. 두 부모 모두 과학적인 사고방식을 지녔기에, 아기 돌봄에도 과학적으로 접근하기로 했다.

Cameron과 Jamie는 매일의 일과를 정하고 있으며, 각 시각에 누가 아기를 주로 책임질지 결정해야 한다. 두 사람은 함께해 온 내내 동등한 동반자였고 지금도 이를 바꾸고 싶지 않으므로, 각자 하루에 정확히 12시간(720분) 동안 아기를 맡기로 했다.

Cameron과 Jamie에게는 각자 혼자 해야 하거나 하고 싶은 다른 활동들이 있다. Cameron에게는 이런 활동이 $A_{C}$개, Jamie에게는 $A_{J}$개 있다. 이 활동들은 매일 항상 같은 시각에 이루어진다. Cameron의 활동과 Jamie의 활동은 서로 겹치지 않으므로, 부모 중 적어도 한 명은 언제나 아기를 돌볼 수 있다.

Cameron과 Jamie는 다음 조건을 만족하는 일일 아기 돌봄 일정을 만들고자 한다.

• 예정된 아기 돌봄 시간은 예정된 활동을 방해해서는 안 된다. 즉, Cameron이 활동하는 동안에는 Jamie가 아기를 맡아야 하며, 그 반대도 마찬가지이다.

• Cameron과 Jamie에게 각각 정확히 720분이 배정되어야 한다.

• 교대 횟수, 즉 아기를 맡는 사람이 한 동반자에서 다른 동반자로 바뀌는 횟수는 가능한 한 작아야 한다.

예를 들어 Jamie와 Cameron에게 각각 활동이 하나씩 있다고 하자. Jamie에게는 오전 9시부터 오전 10시까지의 활동이 있고, Cameron에게는 오후 2시부터 오후 3시까지의 활동이 있다. 가능하지만 최적이 아닌 일정으로, Jamie가 자정부터 오전 6시까지와 정오부터 오후 6시까지 아기를 돌보고, Cameron이 오전 6시부터 정오까지와 오후 6시부터 자정까지 아기를 돌보게 할 수 있다. 이는 앞의 두 조건을 만족하며 자정, 오전 6시, 정오, 오후 6시에 일어나는 총 4번의 교대가 필요하다. 자정에 교대가 일어나면 없거나 두 번이 아니라 정확히 한 번으로 센다.

더 나은 방법은 Cameron이 자정부터 정오까지 아기를 돌보고 Jamie가 정오부터 자정까지 아기를 돌보는 것이다. 이 일정도 앞의 두 조건을 만족하지만, 가능한 최솟값인 2번의 교대만 사용한다.

Cameron과 Jamie의 활동 목록 및 위의 제약이 주어질 때, 일일 일정에서 가능한 최소 교대 횟수는 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i에 대해 0 ≤ $C_{i}$ < $D_{i}$ ≤ 24 × 60. 모든 i에 대해 0 ≤ $J_{i}$ < $K_{i}$ ≤ 24 × 60. 모든 i}에 대한 구간 {[$C_{i}$, $D_{i}$)과 모든 i}에 대한 구간 {[$J_{i}$, $K_{i}$)의 합집합에 속한 임의의 서로 다른 두 구간의 교집합은 공집합이다. (구간은 왼쪽에서 닫히고 오른쪽에서 열려 있으므로, 정확히 연속하는 두 구간 사이에는 아무것도 없지만 두 구간이 겹치지는 않는다.) 모든 i}에 대한 {$D_{i}$ - $C_{i}$의 합 ≤ 720. 모든 i}에 대한 {$K_{i}$ - $J_{i}$의 합 ≤ 720.

소규모 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ $A_{C}$ ≤ 2. 0 ≤ $A_{J}$ ≤ 2. 1 ≤ $A_{C}$ + $A_{J}$ ≤ 2.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ $A_{C}$ ≤ 100. 0 ≤ $A_{J}$ ≤ 100. 1 ≤ $A_{C}$ + $A_{J}$ ≤ 200.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Cameron과 Jamie가 가진 활동의 수를 각각 나타내는 두 정수 $A_{C}$와 $A_{J}$가 포함된 줄로 시작한다. 그다음 $A_{C}$ + $A_{J}$개의 줄이 주어진다. 이 중 처음 $A_{C}$개의 줄에는 각각 두 정수 $C_{i}$와 $D_{i}$가 주어진다. Cameron의 i번째 활동은 자정의 하루 시작 시점으로부터 정확히 $C_{i}$분 후에 시작하고, 자정의 하루 시작 시점으로부터 정확히 $D_{i}$분 후에 끝난다(정확히 $D_{i}$ - $C_{i}$분이 걸린다). 이 중 마지막 $A_{J}$개의 줄에는 각각 두 정수 $J_{i}$와 $K_{i}$가 주어지며, 자정의 하루 시작 시점부터 분 단위로 센 Jamie의 활동 하나의 시작 시각과 종료 시각을 나타낸다(Cameron의 경우와 같은 형식이다). 어떤 활동도 이틀에 걸쳐 이어지지 않으며, 어떤 두 활동도 겹치지 않는다(단, 한 활동이 다른 활동의 시작 시각에 정확히 끝날 수 있으며, 그 시각에도 교대가 일어날 수 있다).

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 문제 설명에 기술된 가능한 최소 교대 횟수이다.

케이스 #4와 #5는 소규모 데이터 세트에 등장하지 않는다는 점에 유의한다.

케이스 #1는 문제 설명에서 다룬 경우이다.

케이스 #2에서는 Jamie가 Cameron의 모든 활동 시간 동안 대신 아기를 맡아야 하고, 그다음 Cameron이 나머지 모든 시간 동안 대신 맡아야 한다. 이 일정에는 네 번의 교대가 따른다.

케이스 #3에서는 자정에 Cameron에서 Jamie로 교대한다. 부모가 하루 중 활동이 없는 나머지 1438분을 어떻게 나누더라도 Jamie에서 Cameron으로 적어도 한 번은 교대해야 하며, 그보다 더 많은 교대를 추가할 이유는 없다.

케이스 #4에서는 같은 동반자 또는 서로 다른 동반자의 활동이 연달아 있을 수 있다는 점에 유의한다. Cameron에게 그 시각의 직전과 직후에 모두 활동이 있으므로 자정에는 교대가 없다. 하지만 일정상 Jamie의 활동들 사이에 Cameron의 시간을 어느 정도 추가해야 하므로 총 4번의 교대가 필요하다. 2분과 1438분 사이 어딘가에 길이가 718인 Cameron의 구간 하나를 추가하는 것이 최적이지만, 추가되는 구간의 정확한 위치는 교대 횟수에 영향을 주지 않으므로 최적 일정이 여러 개라는 점에 유의한다.

케이스 #5에서 가능한 최적 일정 하나는 Cameron에게 (분 단위) 구간 100-200, 500-620, 900-1400를 배정하는 것이다.