주식 거래

주식 거래는 라스베이거스의 하이 스테이크 테이블조차 시시하게 느껴지는 사람에게 돈을 버는 좋은 방법입니다. 원리는 간단합니다. 가격이 쌀 때 사서 비쌀 때 팔면 됩니다. 문제는 다음 순간 가격이 오를지 내릴지 알 수 없다는 것입니다. 하지만 미래를 미리 안다면 문제는 훨씬 쉬워집니다. 여기서는 모든 가격을 이미 알고 있다고 가정하고, 사후적으로 최적의 투자 전략을 찾는 방법을 살펴봅니다.

총 $n$개의 주식과 $D$일이 있습니다. 각 날마다 모든 주식 $i$의 가격이 주어집니다. 처음에 자본금 $C$달러를 가지고 시작합니다. 매일, 현재 자본금을 넘지 않는 범위에서 원하는 종류의 주식을 원하는 만큼 사거나 팔 수 있습니다. 단, 한 가지 규칙이 더 있습니다. 전체 기간 동안 거래는 최대 $t$번까지만 할 수 있습니다. 한 번의 거래란 한 종류의 주식을 사거나 파는 행위를 말합니다. 주식은 정수 단위로 거래할 필요가 없어, 예를 들어 원한다면 어떤 주식을 $1.364$단위만큼 살 수도 있습니다. 같은 날 여러 종류의 주식을 사면 그만큼 여러 번의 거래를 사용합니다. 목표는 $D$일이 끝난 뒤 손에 남은 현금의 총액을 최대화하는 것입니다. (오직 현금만 계산하며, $D$일이 끝난 뒤에도 들고 있는 주식은 아무 가치가 없습니다.)

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

각 데이터 집합의 첫째 줄에는 정수 $n$, $D$, $t$와 실수 $C$가 주어집니다. $1 \le n \le 100$은 주식의 개수, $1 \le D \le 100$은 날의 수, $0 \le t \le 100$은 할 수 있는 거래 횟수, $C \ge 0$은 시작 자본금입니다.

이어서 $D$개의 줄이 주어지며, 각 줄에는 $n$개의 실수 $r_{d,i} \ge 0$이 있습니다. $r_{d,i}$는 $d$번째 날에 주식 $i$가 거래되는 가격입니다. 한 날의 모든 가격은 같은 줄에 나열됩니다.

각 데이터 집합에 대해, 한 줄에 Data Set x:를 출력합니다. 여기서 x는 데이터 집합의 번호($1$부터 시작)입니다. 다음 줄에는 최대 $t$번의 거래로 $D$일이 끝난 뒤 가질 수 있는 최대 금액을 소수점 아래 둘째 자리까지 반올림하여 출력합니다. 연속한 데이터 집합 사이에는 빈 줄을 하나 출력합니다.