Problem E
The Lonesome Cargo Distributor
Input: standard input
Output: standard output
Time Limit: 3 seconds
The Plussians believe that the Airport Based Cargo Distribution & Embarkation Facility (ABCDEF in short) at the Cosco International Airport (CIA) is the largest such facility in the whole world though second largest in Plussia. Cargo planes arrive from and leave for many countries all around the world (Cermany, Q.S.A, Capan, Custralia etc. are some to name). ABCDEF is engaged in distributing, loading and unloading the cargoes carried by these planes.
Each cargo is a cubic box of fixed size and has a tag attached to it naming the destination country. For convenience, each country is assigned a unique ID. For example, if there are n countries, each country gets a unique integer ID ranging from 1 to n.
Every country X has its own cargo station identified by its country ID. There are two platforms (platform A and platform B) in each station. In platform A are put those cargoes which are to be transported (by air) to country X at some convenient time. Platform B is actually a queue of cargoes which are to be carried to countries other than country X. The cargo stations have a circular (ring) arrangement, that is, if there are n stations then each of the following station-pairs are adjacent: (1, 2), (2, 3), (3, 4), ..., (n - 1, n) and (n, 1).
ABCDEF has many land-based cargo carriers used to carry cargo from station to station. But these carriers have so narrow space that you cannot even put two cargoes side by side. A carrier can carry more than one cargo (although there is a limit on the maximum number of cargoes a carrier can carry) only by putting them (the cargoes) on top of one another. This stack arrangement has the problem that you cannot just remove any cargo from the stack as you wish. For example, to remove the 3rd cargo from the top you must first remove the topmost two cargoes.
A cargo carrier moves from station to station strictly following their ring arrangement, that is, from station 1 it moves to station 2, then to 3, then 4, ..., then n, then 1 again, etc.. It requires exactly 2 minutes to move from any station to its adjacent one.
After reaching any station (say, station X), the cargo carrier first attempts to unload cargo. Starting from the topmost cargo in its stack, it checks the tag attached to the cargo. If it finds that the cargo has destination X, then it unloads it (the cargo) to platform A, otherwise it checks to see whether the queue in platform B has any vacant position, and if so it puts the cargo at the rear of the queue. This unloading procedure continues from the top to the bottom of the stack until one fails or the stack becomes empty, whichever comes first. Each successful unloading attempt requires exactly 1 minute, that is, unloading 3 cargoes in a station will require exactly 3 minutes. After unloading is complete, the carrier begins to load. The carrier continues to take the cargo in front of the queue in platform B and put it on top of its stack until the queue is empty or the stack is full, whichever comes first. Each successful loading attempt also requires exactly 1 minute, that is, loading 4 cargoes from a station will require exactly 4 minutes. After loading is complete, the carrier moves to the next station in the ring.
In this way, for many years, the cargo carriers are doing the job of moving the cargoes from platform B to platform A of appropriate stations from where the cargo planes carry them (the cargoes) to their destination countries.
But, after a conflict with the management regarding the pay scale, the employees of ABCDEF have gone to a strike for indefinite period from the last Sunday. Planes are arriving and leaving, but no one is there to load and unload the cargo. There is no one to distribute the queued cargoes to their destination stations. The entire facility has now come to a standstill.
But, you, as always known to and hated by your colleagues as the boss's man, have decided to break the strike and save CIA. You are going to start working from tomorrow morning and distribute the queued cargoes to their appropriate stations using a cargo carrier. Initially your carrier will be empty and, you will start your journey from station 1 and continue to move around the ring until all the cargoes have been distributed to their destination stations. But before starting the job, you have decided to write a program to determine exactly how long it will take to complete it.
The input contains several sets of input. The first line of the input file contains an integer SET, which indicates how many sets of inputs are there. It is then followed by SET sets of inputs. In our sample input the value of SET is 2.
The first line of the input contains three integers: N, S and Q. N (2 <= N <= 100) is the number of stations in the ring. S (1 <= S <= 100) is the capacity of your cargo carrier, that is, the maximum number of cargoes your carrier can carry. Q (1 <= Q <= 100) is the maximum number of cargoes the queue in platform B can accommodate. All the queues in the system are assumed to have the same capacity.
Then follow N lines. Assuming that these lines are numbered from 1 to N, for 1 <= i <= N, line i contains an integer Qi (0 <= Qi <= Q) giving the number of cargoes queued at station i followed by Qi integers giving the destination stations of the queued cargoes from front to rear. You may assume that none of these Qi cargoes will have station i as their destination.
For each set of input output the number of minutes it will take to finish the job in a separate line.
“All good things must come to an end.”