시추 장비 배치

기름이 어디에 있는지 이미 알아냈고, 나아가 각 위치에 기름이 얼마나 있는지까지 알고 있다고 하자. 이제 남은 질문은 시추 장비(rig)를 어디에 배치할 것인가이다. 장비가 폭발한 뒤 최대한 많은 기름을 뽑아내는 것이 목표이며, 이는 생각만큼 단순하지 않다.

문제를 다음과 같이 모델링한다. 개발 대상이 될 수 있는 유전이 $n$개 있다($1 \le n \le 100$). 각 유전에 대해 백만 달러 단위로 $0$부터 $m$까지의 금액을 투자할 수 있다($m$은 한 유전에 투자할 수 있는 최대 금액이다). 각 유전 $i$($1 \le i \le n$)와 각 투자 금액 $j \in {0, 1, 2, \dots, m}$에 대해, 표 $a[i, j]$는 그때 얻는 기름의 양(음이 아닌 실수)을 나타낸다. 표의 값은 $j$에 대해 단조 비감소한다(돈을 더 쓰면 최소한 이전만큼의 기름은 얻는다). 그 밖에는 임의의 값일 수 있다. 시추에 쓸 수 있는 전체 예산은 정수 $B$이며 $0 \le B \le 100$이다(역시 백만 달러 단위). 주어진 예산으로 뽑아낼 수 있는 기름의 최대 총량을 구하라.

첫 줄에는 데이터 집합의 개수 $K$가 주어지고, 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 세 정수 $n$, $m$, $B$가 주어진다. 각각 유전의 개수, 한 유전당 최대 투자 금액, 전체 예산이다.

이어서 $n$개의 줄이 주어지며, 각 줄에는 $m + 1$개의 음이 아닌 실수가 있다. $i$번째 줄의 $j$번째 수($j = 0, 1, \dots, m$)는 $i$번째 유전에 $j$백만 달러를 투자했을 때 뽑아낼 수 있는 기름의 양이다.

각 데이터 집합에 대해, 한 줄에 Data Set x:를 출력한다($x$는 그 데이터 집합의 번호). 다음 줄에는 주어진 조건에서 뽑아낼 수 있는 기름의 최대 총량을 소수점 아래 둘째 자리까지 반올림하여 출력한다. 서로 이웃한 두 데이터 집합 사이에는 빈 줄을 하나 넣는다.