재료 최적화

Hathai는 자신의 출장 음식 서비스가 마을에서 가장 신선한 음식을 제공한다는 사실을 자랑스럽게 여긴다. 이를 위해 방부제가 없는 신선한 재료를 계속 배달받는다. 이로 인해 재료가 상하지 않도록 해야 하는 문제가 생긴다. 현재의 특별 요리에는 특별한 관리가 필요한 타이 바질 잎이 정확히 $\mathbf{U}$장 사용된다.

Hathai는 타이 바질의 배달 일정을 알고 있다. $i$번째 배달은 영업 시작 후 분 단위 시각인 $\mathbf{M_i}$의 시작에 도착하며, 도착한 뒤 최대 $\mathbf{E_i}$분 동안 보관할 수 있는 타이 바질 잎을 정확히 $\mathbf{L_i}$장 가져온다. Hathai는 시각 $\mathbf{O_1}, \mathbf{O_2}, \dots, \mathbf{O_N}$에 자신의 특별 요리를 준비해야 하는 주문들을 받았다. 주문 $i$은 시각 $\mathbf{O_i}$에 상하지 않은 타이 바질 잎이 $\mathbf{U}$장 있어야만 처리할 수 있다. 잎이 주문이 들어오는 것과 같은 시각에 상한다면, 그 잎은 해당 주문을 처리하는 데 사용할 수 없다는 점에 유의한다. 주문을 처리하면, 사용 가능한 잎 중 $\mathbf{U}$장을 사용해야 하며 이후의 주문에는 사용할 수 없다. Once Hathai가 처리할 수 없는 주문을 받으면, 주방을 닫고 주문 처리 일정을 개선할 방법을 생각해야 하므로 남은 모든 주문도 취소된다.

예를 들어, Hathai의 일정에 다음과 같은 $4$번의 배달이 있다고 하자.

• 배달 시각: $1$. 양: $10$. 상하기까지 남은 시간: $2$.

• 배달 시각: $3$. 양: $4$. 상하기까지 남은 시간: $2$.

• 배달 시각: $5$. 양: $1$. 상하기까지 남은 시간: $4$.

• 배달 시각: $10$. 양: $6$. 상하기까지 남은 시간: $3$.

또한 시각 $3$, $4$, $6$, $10$에 접수된 주문이 $4$개 있다고 하자. 이 예제에서 각 주문에는 잎 $\mathbf{U}=2$장을 사용해야 한다.

첫 번째 배달분은 시각 $3$에 상하므로 어떤 주문에도 사용할 수 없다. 이후 시각 $3$의 첫 번째 주문과 시각 $4$의 두 번째 주문을 처리할 수 있으며, 두 번째 배달로 받은 잎 $4$장을 모두 사용한다. 시각 $6$의 세 번째 주문 때는 보관 중인 잎이 $1$장뿐이므로 Hathai는 이 주문을 처리할 수 없다. 시각 $10$에 배달이 있더라도 Hathai는 이미 주방을 닫았으므로 시각 $10$의 네 번째 주문도 처리할 수 없다는 점에 유의한다. 이 예제에서 Hathai는 총 $2$개의 주문을 처리했다.

배달 일정과 주문 일정이 주어질 때, Hathai가 타이 바질 잎의 사용을 최적화하여 처리할 수 있는 주문 수의 최댓값을 구한다.

제한

시간 제한: 5초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{D} \le 100$. $1 \le \mathbf{N} \le 100$. $1 \le \mathbf{U} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{M_i} \le 10^9$. 모든 $i$에 대해 $\mathbf{M_i} \lt \mathbf{M_{i+1}}$. (배달은 시각이 증가하는 순서로 주어진다.) 모든 $i$에 대해 $1 \le \mathbf{L_i} \le 100$. 모든 $j$에 대해 $1 \le \mathbf{O_j} \le 10^9$. 모든 $j$에 대해 $\mathbf{O_j} \lt \mathbf{O_{j+1}}$. (주문은 시각이 증가하는 순서로 주어진다.)

테스트 세트 1 (Visible Verdict)

모든 $i$에 대해 $\mathbf{E_i} = 10^9$. (주문이 들어오기 전에 상하는 타이 바질 잎은 없다.)

테스트 세트 2 (Hidden Verdict)

모든 $i$에 대해 $1 \le \mathbf{E_i} \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 $\mathbf{D}$, $\mathbf{N}$, $\mathbf{U}$이 포함된 한 줄로 시작하며, 각각 배달 횟수, 주문 수, 각 주문에 필요한 잎의 양을 나타낸다. 그다음 $\mathbf{D}$개의 줄이 주어진다. 이 줄들 중 $i$번째 줄에는 세 정수 $\mathbf{M_i}$, $\mathbf{L_i}$, $\mathbf{E_i}$이 주어지며, 각각 $i$번째 배달의 영업 시작 후 분 단위 배달 시각, 배달된 타이 바질 잎의 양, 해당 잎을 신선한 상태로 보관할 수 있는 시간(분)을 나타낸다. 그다음 마지막 줄에는 $\mathbf{N}$개의 정수 $\mathbf{O_1}, \mathbf{O_2}, \dots, \mathbf{O_N}$가 주어지며, $\mathbf{O_j}$는 $j$번째 주문을 준비해야 하는 영업 시작 후 분 단위 시각이다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 (1부터 시작하는) 테스트 케이스 번호이고, $y$는 Hathai가 처리할 수 있는 주문 수의 최댓값을 나타내는 정수이다.

샘플 케이스 #1에서 첫 번째 주문은 어떤 배달로도 타이 바질 잎이 들어오기 전에 너무 일찍 도착했으므로 Hathai는 이를 처리할 수 없다. 따라서 주문을 하나도 처리하지 못한 채 즉시 주방을 닫아야 한다.

샘플 케이스 #2에서 Hathai는 첫 번째 주문을 처리할 수 있고, 두 번째 배달이 두 번째 주문을 처리하는 데 도움이 되도록 딱 맞춰 도착한다. 하지만 매우 많은 양의 세 번째 배달은 세 번째 주문에 도움이 될 만큼 제때 도착하지 않으므로 그 주문은 처리되지 않으며, 남은 주문들도 마찬가지다.

추가 샘플 - 테스트 세트 2

이 추가 샘플은 문제 설명에서 설명한 샘플이다.