Pump up Batteries

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem D: Pump up Batteries

Bill is a boss of security guards. He has pride in that his men put on wearable computers on their duty. At the same time, it is his headache that capacities of commercially available batteries are far too small to support those computers all day long. His men come back to the office to charge up their batteries and spend idle time until its completion. Bill has only one battery charger in the office because it is very expensive.

Bill suspects that his men spend much idle time waiting in a queue for the charger. If it is the case, Bill had better introduce another charger. Bill knows that his men are honest in some sense and blindly follow any given instructions or rules. Such a simple-minded way of life may lead to longer waiting time, but they cannot change their behavioral pattern.

Each battery has a data sheet attached on it that indicates the best pattern of charging and consuming cycle. The pattern is given as a sequence of pairs of consuming time and charging time. The data sheet says the pattern should be followed cyclically to keep the battery in quality. A guard, trying to follow the suggested cycle strictly, will come back to the office exactly when the consuming time passes out, stay there until the battery has been charged for the exact time period indicated, and then go back to his beat.

The guards are quite punctual. They spend not a second more in the office than the time necessary for charging up their batteries. They will wait in a queue, however, if the charger is occupied by another guard, exactly on first-come-first-served basis. When two or more guards come back to the office at the same instance of time, they line up in the order of their identifi- cation numbers, and, each of them, one by one in the order of that line, judges if he can use the charger and, if not, goes into the queue. They do these actions in an instant.

Your mission is to write a program that simulates those situations like Billfs and reports how much time is wasted in waiting for the charger.


The input consists of one or more data sets for simulation.

The first line of a data set consists of two positive integers separated by a space character: the number of guards and the simulation duration. The number of guards does not exceed one hundred. The guards have their identification numbers starting from one up to the number of guards. The simulation duration is measured in minutes, and is at most one week, i.e., 10080 (min.).

Patterns for batteries possessed by the guards follow the first line. For each guard, in the order of identification number, appears the pattern indicated on the data sheet attached to his battery. A pattern is a sequence of positive integers, whose length is a multiple of two and does not exceed fifty. The numbers in the sequence show consuming time and charging time alternately. Those times are also given in minutes and are at most one day, i.e., 1440 (min.). A space character or a newline follows each number. A pattern is terminated with an additional zero followed by a newline.

Each data set is terminated with an additional empty line. The input is terminated with an additional line that contains two zeros separated by a space character.


For each data set your program should simulate up to the given duration. Each guard should repeat consuming of his battery (i.e., being on his beat) and charging of his battery according to the given pattern cyclically. At the beginning, all the guards start their cycle simultaneously, that is, they start their beats and, thus, start their first consuming period.

For each data set, your program should produce one line containing the total wait time of the guards in the queue up to the time when the simulation duration runs out. The output should not contain any other characters.

For example, consider a data set:

3 25
3 1 2 1 4 1 0
1 1 0
2 1 3 2 0

The guard 1 tries to repeat 3 min. consuming, 1 min. charging, 2 min. consuming, 1 min. charging, 4 min. consuming, and 1 min. charging, cyclically. Yet he has to wait sometimes to use the charger, when he is on his duty together with the other guards 2 and 3. Thus, the actual behavior of the guards looks like:

         0         10        20
         |    |    |    |    |    |
guard 1: ***.**.****.***.**-.****.
guard 2: *.*-.*-.*-.*.*.*.*--.*.*-
guard 3: **.***--..**-.***..**.***

where g*h represents a minute spent for consuming, g.h for charging, and g-h for waiting in the queue. At time 3, the guards 1 and 2 came back to the office and the guard 1 started charging while the guard 2 went into the queue. At time 6, all the guards came back to the office and the guard 1 started charging while the others went to the queue. When the charger got available at time 7, the guard 2 started charging, leaving the guard 3 in the queue. All those happened are consequences of rules stated above. And the total time wasted in waiting for the charger becomes 10 minutes.

Sample Input

3 25
3 1 2 1 4 1 0
1 1 0
2 1 3 2 0

4 1000
80 20 80 20 80 20 80 20 0
80 20 90
10 80
90 10

0 0

Output for the Sample Input


Source: ACM International Collegiate Programming Contest , Asia Regional Tsukuba, Tsukuba, Japan, 2000-11-12