Stock Trading

Stock trading is a great way to make money if you think the high-stakes tables in Las Vegas are not risky enough for you. The idea is simple: buy stock when the price is low, and sell when it is high. The only catch is that you do not know whether the price will go up or down next. But if you did, the problem would be much easier. Here we assume all prices are known in advance and explore how to find an optimal investment strategy in retrospect.

There are $n$ stocks in total and $D$ days. On each day you are given the price of every stock $i$. You start with a capital of $C$ dollars. On each day you may buy or sell arbitrary amounts of any combination of stocks, of course never spending more than your current capital. There is one more rule: you may make at most $t$ trades in total. A trade is the act of buying or selling one kind of stock. You do not have to trade in integer amounts; for example you may buy $1.364$ units of a stock if you want. Buying several kinds of stock on the same day uses several trades. Your goal is to maximize the total amount of cash you hold after $D$ days. (Only cash counts; any stock you still hold after $D$ days is worthless.)

The first line contains the number $K$ of data sets, followed by the $K$ data sets, each in the following form.

The first line of a data set contains integers $n$, $D$, $t$ and a floating point number $C$. Here $1 \le n \le 100$ is the number of stocks, $1 \le D \le 100$ is the number of days, $0 \le t \le 100$ is the number of trades you may make, and $C \ge 0$ is your starting capital.

This is followed by $D$ lines, each containing $n$ floating point numbers $r_{d,i} \ge 0$. The value $r_{d,i}$ is the price at which stock $i$ trades on day $d$. All prices for one day appear on the same line.

For each data set, print a line Data Set x: by itself, where x is the data set number (starting from $1$). On the next line, print the maximum amount of money you can have after the $D$ days, rounded to two decimals, having made at most $t$ trades in total. Print a blank line between consecutive data sets.