재료 최적화

하타이는 자신이 운영하는 케이터링 서비스가 도시에서 가장 신선한 음식을 제공한다는 점을 자랑스럽게 여긴다. 이를 위해 방부제가 없는 신선한 재료를 계속 배송받는다. 문제는 재료가 상하지 않도록 막는 것이다. 그녀의 특제 요리에는 정확히 $U$장의 태국 바질 잎이 필요하며, 이 잎은 특별히 관리해야 한다.

하타이는 태국 바질 배송 일정을 알고 있다. $i$번째 배송은 영업 시작 후 $M_i$분 시점의 시작에 도착한다. 정확히 $L_i$장의 잎을 가져오며, 이 잎은 도착한 뒤 최대 $E_i$분 동안 보관할 수 있다.

하타이에게는 $O_1, O_2, \dots, O_N$ 시점에 특제 요리를 준비해 달라는 주문이 들어와 있다. $i$번째 주문은 $O_i$ 시점에 상하지 않은 잎이 $U$장 있어야만 처리할 수 있다. 잎이 주문이 들어오는 시점과 같은 시점에 상한다면, 그 잎은 그 주문에 쓸 수 없다. 주문을 처리하면 사용 가능한 잎 중 $U$장을 쓰며, 쓴 잎은 이후 주문에 다시 쓸 수 없다. 처리할 수 없는 주문을 한 번이라도 받으면 하타이는 주방을 닫고 일정을 어떻게 개선할지 고민하므로, 그 뒤의 주문은 모두 취소된다.

예를 들어 하타이의 배송 일정이 다음 4건이라고 하자.

• 배송 시점: 1. 수량: 10. 상하기까지 남은 시간: 2.
• 배송 시점: 3. 수량: 4. 상하기까지 남은 시간: 2.
• 배송 시점: 5. 수량: 1. 상하기까지 남은 시간: 4.
• 배송 시점: 10. 수량: 6. 상하기까지 남은 시간: 3.

또 하타이에게 시점 3, 4, 6, 10에 주문 4건이 들어왔다고 하자. 이 예시에서는 주문마다 $U=2$장의 잎이 필요하다.

첫 번째 배송은 시점 3에 상하므로 어떤 주문에도 쓸 수 없다. 시점 3과 시점 4의 주문은 두 번째 배송의 잎 4장으로 처리할 수 있다. 시점 6의 주문은 보관 중인 잎이 1장뿐이라 처리할 수 없다. 시점 10의 주문은 이미 주방을 닫았으므로 처리하지 않는다. 이 예시에서 하타이가 처리한 주문은 모두 2건이다.

하타이가 태국 바질 잎을 최적으로 사용한다면 처리할 수 있는 주문의 최대 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 배송 수 $D$, 주문 수 $N$, 주문마다 필요한 잎의 수 $U$를 나타내는 세 정수로 시작한다.

이어서 $D$개의 줄이 주어진다. $i$번째 줄에는 배송 시점 $M_i$ (영업 시작 후 분 단위), 배송된 잎의 수 $L_i$, 잎이 신선하게 보관되는 시간 $E_i$ (분 단위)가 주어진다.

마지막 줄에는 $N$개의 정수 $O_1, O_2, \dots, O_N$이 주어진다. $O_j$는 $j$번째 주문을 준비해야 하는 시점 (영업 시작 후 분 단위)이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 하타이가 처리할 수 있는 주문의 최대 개수다.

• $1 \le T \le 100$.
• $1 \le D \le 100$.
• $1 \le N \le 100$.
• $1 \le U \le 100$.
• 모든 $i$에 대해 $1 \le M_i \le 10^9$.
• 모든 $i$에 대해 $M_i < M_{i+1}$. 배송은 시점의 오름차순으로 주어진다.
• 모든 $i$에 대해 $1 \le L_i \le 100$.
• 모든 $j$에 대해 $1 \le O_j \le 10^9$.
• 모든 $j$에 대해 $O_j < O_{j+1}$. 주문은 시점의 오름차순으로 주어진다.