Pump up Batteries

Bill is the boss of a group of security guards. He takes pride in the fact that his men wear wearable computers on duty. At the same time, he is troubled that commercially available batteries have far too little capacity to power those computers all day. His men come back to the office to charge their batteries and spend idle time until charging finishes. Bill has only one battery charger in the office because it is very expensive.

Bill suspects that his men waste a lot of idle time waiting in a queue for the charger. If that is the case, he would be better off introducing another charger. Bill knows that his men are honest in a certain sense and blindly follow any instructions or rules they are given. This simple-minded way of life may lead to longer waiting times, but they cannot change their behavioral pattern.

Each battery has a data sheet attached to it that indicates the best pattern of the 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 good condition. A guard who tries to follow the suggested cycle strictly comes back to the office exactly when the consuming time passes, stays there until the battery has been charged for the exact time period indicated, and then goes back to his beat.

The guards are quite punctual. They spend not a second more in the office than the time necessary to charge their batteries. They wait in a queue, however, if the charger is occupied by another guard, exactly on a first-come-first-served basis. When two or more guards come back to the office at the same instant, they line up in the order of their identification numbers, and each of them, one by one in the order of that line, judges whether 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 situations like Bill's and reports how much time is wasted 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 identification numbers starting from one up to the number of guards. The simulation duration is measured in minutes, and is at most one week, that is, 10080 minutes.

Patterns for the batteries possessed by the guards follow the first line. For each guard, in the order of identification number, the pattern indicated on the data sheet attached to his battery appears. 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, that is, 1440 minutes. 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 his battery (that is, being on his beat) and charging 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

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 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 "*" represents a minute spent consuming, "." charging, and "-" waiting in the queue. At time 3, guards 1 and 2 came back to the office and guard 1 started charging while guard 2 went into the queue. At time 6, all the guards came back to the office and guard 1 started charging while the others went to the queue. When the charger became available at time 7, guard 2 started charging, leaving guard 3 in the queue. All of that happened as a consequence of the rules stated above. The total time wasted waiting for the charger becomes 10 minutes.