시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)129872.727%

문제

Hathai is proud that her catering service provides the freshest food in town. To accomplish that, she gets fresh ingredients with no preservatives delivered constantly. This brings about the challenge of preventing the ingredients from spoiling. Her current special uses exactly $U$ leaves of Thai basil, that need special care.

Hathai has the schedule of the deliveries of Thai basil. The $i$-th delivery comes at the beginning of time $M_i$ (in minutes since opening time), and brings exactly $L_i$ leaves of Thai basil that can be stored for at most $E_i$ minutes since arriving. Hathai has orders to prepare her specialty dish at times $O_1,O_2, \dots ,O_N$. Order $i$ can only be fulfilled if she has $U$ unspoiled leaves of Thai basil at time $O_i$. Note that if leaves would spoil at the same time an order comes in, those leaves cannot be used to fulfill that order. If an order is fulfilled, $U$ of the leaves available have to be used and cannot be used for future orders. Once Hathai gets an order that she cannot fulfill, all of the remaining orders will also be canceled because she needs to close her kitchen and think about how to improve the fulfillment schedule.

For example, suppose Hathai's schedule has the following $4$ deliveries:

  • Delivery time: $1$. Amount: $10$. Time remaining until spoiled: $2$.
  • Delivery time: $3$. Amount: $4$. Time remaining until spoiled: $2$.
  • Delivery time: $5$. Amount: $1$. Time remaining until spoiled: $4$.
  • Delivery time: $10$. Amount: $6$. Time remaining until spoiled: $3$.

And also suppose she has $4$ orders placed at times $3$, $4$, $6$ and $10$. Each order requires using $U=2$ leaves in this example.

The first delivery become spoiled at time $3$, so it cannot be used on any order. Then the first order and the second order at time $3$ and time $4$ can be fulfilled and use up the $4$ leaves from the second delivery. For the third order at time $6$, there is only $1$ leaf in the storage, so Hathai cannot fulfill this order. Note that although there is a delivery at time $10$, she still cannot fulfill the fourth order at time $10$ because she has already closed her kitchen. In this example, Hathai managed to fulfill $2$ orders in total.

Given the delivery and order schedules, find out the maximum number of orders Hathai can fulfill if she optimizes the use of the Thai basil leaves.

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing three integers $D$, $N$, and $U$: the number of deliveries, the number of orders and the amount of leaves needed for each order, respectively. Then, $D$ lines follow. The $i$-th of these lines contains three integers $M_i$, $L_i$, and $E_i$: the time of the delivery in minutes since opening time, the amount of Thai basil leaves delivered, and the number of minutes those leaves can be stored and remain fresh, respectively, of the $i$-th delivery. Then, the last line contains $N$ integers $O_1,O_2, \dots ,O_N$, where $O_j$ is the time, in minutes since opening time, at which the $j$-th order must be prepared.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is an integer representing the maximum number of orders Hathai can fulfill.

제한

  • $1≤T≤100$.
  • $1≤D≤100$.
  • $1≤N≤100$.
  • $1≤U≤100$.
  • $1≤M_i≤10^9$, for all $i$.
  • $M_i<M_{i+1}$, for all $i$. (Deliveries are given in increasing order of time.)
  • $1≤L_i≤100$, for all $i$.
  • $1≤O_j≤10^9$, for all $j$.
  • $O_j<O_{j+1}$, for all $j$. (Orders are given in increasing order of time.)

Test Set 1 (8점)

  • $E_i=10^9$, for all $i$. (No Thai basil leaf expires before an order comes.)

Test Set 2 (14점)

  • $1≤E_i≤10^9$, for all $i$.

예제 입력 1

2
2 4 5
20 8 1000000000
60 4 1000000000
10 30 50 70
3 5 5
20 8 1000000000
50 3 1000000000
60 100 1000000000
30 50 59 70 90

예제 출력 1

Case #1: 0
Case #2: 2

In Sample Case #1, Hathai cannot fulfill the first order, because it came too early, before any deliveries brought in Thai leaves. So she has to close her kitchen immediately without fulfilling any order.

In Sample Case #2, Hathai can fulfill the first order, and her second delivery arrives just in time to help her fulfill the second order. However, the huge third delivery does not get to her in time to help her with the third order, so that one goes unfulfilled and so do the remaining ones.

예제 입력 2

1
4 4 2
1 10 2
3 4 2
5 1 4
10 6 3
3 4 6 10

예제 출력 2

Case #1: 2

This additional sample is the one explained in the problem statement.

채점 및 기타 정보

  • 예제는 채점하지 않는다.