Segment Pricing

You run a subway line and want to set fares that maximize revenue, assuming you know exactly who will ride and each rider's budget.

The line has $n$ stops and therefore $n - 1$ segments between consecutive stops. For simplicity, every rider is heading to the final stop $n$, but riders board at different stops. You must choose a fare for each boarding stop $i$ (for $1 \le i \le n - 1$).

For fairness, a stop farther from the destination may not be cheaper than one closer to it: the fare at stop $i$ must be at least the fare at stop $i + 1$, since it covers a longer distance.

For each stop you are given the exact budget of every rider who wants to board there. A rider boards only if their budget is at least that stop's fare; otherwise they walk and pay nothing. No fare may exceed $5.00 (that is, $500$ cents), and every fare is between $0$ and $500$ cents. The subway always has enough seats for everyone.

Maximize the total revenue, where the revenue collected at a stop is its fare multiplied by the number of riders who board there.

The first line contains the number of data sets $K$. Each data set has the following form:

• The first line contains an integer $n$ ($2 \le n \le 100$), the number of stops.
• The next $n - 1$ lines describe the boarding riders; line $i$ lists the riders boarding at stop $i$ (all of whom get off at stop $n$). That line contains $m_i$ integers ($0 \le m_i \le 100$): the budgets $b_j \ge 0$ (in cents) of those riders, given in non-decreasing order. An empty line means no rider boards at that stop.

A budget may exceed $500$; such a rider still boards at any fare up to the $500$-cent cap.

For each data set, print Data Set x: on its own line, where $x$ is the data set's number (starting at $1$), then print the maximum revenue in cents on the next line. Separate consecutive data sets with a single blank line.