The My-way-or-the-Highway Trucking company has filed for bankruptcy. As part of the settlement, all of the company's trucks are being purchased by a rival company (Wheels of Fortune). Wheels of Fortune is eager to get their new trucks on the road, but they need to get all of them from their old home base to the new Wheels-of-Fortune headquarters. The limiting factor in this truck-moving task is the capacity of the roads around the headquarters.
You have been contracted to help Wheels of Fortune with this problem. In the course of its business, the company has developed accurate estimates of how many trucks will be able to traverse various roads at different hours of the day. With that information they would like you to calculate the number of trucks that they can expect to arrive at the shipping centers for each of those hours.
The input for this problem consists of (1) a line containing the number (an integer) of hours H for which the road capacities are modeled. For each hour, there follows, on a single line, the number of available interchanges (N) -- spots at which the trucks can switch from one road to another. Following that line are N lines of N whitespace-separated integers. (N will be no larger than 100.) The jth integer on the ith such line will indicate the maximum number of trucks that will be able to make it from the ith to the jth interchange at that particular hour of the day. Thus, the input is the matrix of road capacities.
If there is no road connecting the two interchanges (or if i == j), the capacity will be 0. You may assume that the first line (i = 1) will represent the trucks' origin and that the last line (i = N) represents the goal, the shipping center. This pattern of inputs repeats H times, one for each modeled hour. (Note that the number of interchanges may change from hour to hour as roads open or close.)
There should be one output line for each modeled hour -- it should contain only the largest number of trucks that traffic conditions will permit to reach the shipping center from their starting point in that hour.
2 4 0 10000 10000 0 0 0 1 10000 0 1 0 10000 0 0 0 0 6 0 16 13 0 0 0 0 0 10 12 0 0 0 4 0 0 14 0 0 0 9 0 0 20 0 0 0 7 0 4 0 0 0 0 0 0
20000 23