Problem D: Sampling the Bon Accord

A thirsty programmer has stumbled across a place that sells a variety
of fine refreshments. Being inclined to experiment, she would like to
sample as many different kinds as she can, but will only try one per
night. Planning is made difficult by the fact that the change in
varieties is not regular, but is instead dictated by what is
available.

The place has T spots for refreshment. When a spot becomes vacant,
which only happens when its current type runs out, it is filled with
the next available type from a queue. Types can be repeated.

After some research, our programmer has come up with some additional
information.  First, each type of refreshment lasts exactly for a
positive integer number of days, which will vary. Most importantly,
she has discovered the list of the queue of types, in the order in
which they will be used, together with how many days each will
last. Note that a type may not always last for the same number of
days.

She is willing to visit this place on as many days as are required,
but will only sample once on each day. She needs your help (since this
obsession is compromising her coding skills) to work out the largest
number of different samples that she can try. Note that you only need
to tell her how many; getting a maximum sampling is up to her.

Input Description:

The first line will contain a single number K that will indicate the
number of different test cases to be computed. Blank lines may also
separate the test cases.

Each of the K test cases will contain the following:

The first line of the case will have four numbers: T, the number of
different spots that can be available on each day; D, the total number
of days for which this case will run; B, the total number of different
types of refreshment; and Q, the length of the queue. What follows
will be a list of Q pairs, each giving a type (numbered from 0 to B-1)
followed by how many days it will last.

Note that types can be reused (if they get more) but may not last for
the same duration as before (if a different amount is available, or
its popularity changes). The spots start empty, so the first T types
in the queue are put into use immediately. Slots can be vacant at the
end of the time period if there is nothing left in the queue to
replace them.

Your output should consist of, for each case, a statement that says
how many different samples are possible. Number your cases from 1.

Sample Input:
2
3 6 5 8
0 3
1 2
2 1
3 6
4 4
2 2
0 1
1 3

2 6 5 6
1 3
0 2
2 3
0 2
3 2
4 1


Consider this last case to illustrate how the spots are filled over
its 6 days, as follows:

day 0: type 1, type 0
day 1: type 1, type 0
day 2: type 1, type 2
day 3: type 0, type 2
day 4: type 0, type 2
day 5: type 3, type 4

We have enough of type 3 for one more day, but the sampling period is over.

Sample Output:
Case 1: 5 different samples are possible.
Case 2: 4 different samples are possible.


Our contest software this year requires all data sets to be in one
file (D.in for this problem). You should put a copy of D.in in the
directory with your program.  However your program should take input
from System.in/stdin/cin. This will be connected to D.in when you
submit.