구간 요금 책정

지하철 노선을 운영하면서, 누가 탑승할지와 각 승객의 예산을 정확히 안다고 가정할 때 수익을 최대화하는 요금을 정하려고 합니다.

노선에는 정류장이 $n$개 있으므로 인접한 정류장 사이의 구간은 $n - 1$개입니다. 문제를 단순화하기 위해 모든 승객은 마지막 정류장 $n$까지 가지만, 서로 다른 정류장에서 탑승합니다. 각 출발 정류장 $i$ ($1 \le i \le n - 1$)마다 요금을 하나씩 정해야 합니다.

공정성을 위해, 목적지에서 더 먼 정류장의 요금이 더 가까운 정류장보다 쌀 수는 없습니다. 즉 정류장 $i$의 요금은 정류장 $i + 1$의 요금 이상이어야 하며, 이는 더 긴 거리를 이동하기 때문입니다.

각 정류장마다 그곳에서 타려는 모든 승객의 예산이 정확히 주어집니다. 승객은 자신의 예산이 해당 정류장의 요금 이상일 때에만 탑승하고, 그렇지 않으면 걸어가며 요금을 내지 않습니다. 어떤 요금도 $5.00(즉 $500$센트)를 넘을 수 없으며, 모든 요금은 $0$센트 이상 $500$센트 이하입니다. 지하철에는 항상 모두가 앉을 자리가 충분합니다.

한 정류장에서 얻는 수익은 그 요금에 그곳에서 탑승하는 승객 수를 곱한 값이며, 전체 수익의 합을 최대화하세요.

첫 번째 줄에는 데이터 집합의 수 $K$가 주어집니다. 각 데이터 집합은 다음과 같은 형식입니다.

• 첫 번째 줄에는 정류장의 수를 나타내는 정수 $n$ ($2 \le n \le 100$)이 주어집니다.
• 이어지는 $n - 1$개의 줄은 탑승 승객을 나타내며, $i$번째 줄은 정류장 $i$에서 타는 승객들(모두 정류장 $n$에서 내림)을 설명합니다. 이 줄에는 $m_i$개의 정수 ($0 \le m_i \le 100$), 즉 해당 승객들의 예산 $b_j \ge 0$(센트 단위)가 비내림차순으로 주어집니다. 빈 줄은 그 정류장에서 타는 승객이 없음을 뜻합니다.

예산은 $500$을 넘을 수 있으며, 그런 승객도 $500$센트 상한 이하의 어떤 요금에도 탑승합니다.

각 데이터 집합에 대해 한 줄에 Data Set x:를 출력합니다. 여기서 $x$는 데이터 집합의 번호($1$부터 시작)입니다. 다음 줄에는 최대 수익(센트 단위)을 출력합니다. 연속된 데이터 집합 사이는 빈 줄 하나로 구분합니다.