Maximizing Profit on a Multi-Stop Trading Route

Blue leads a fleet that passes through \(n\) locations sequentially. His ship has a capacity of \(k\) units, and there are \(m\) types of goods. At each location, each good has a different price, and some goods may not be traded at some locations (represented by an unavailable marker, e.g. -1).

Initially, the ship is empty. At every location, Blue may buy any amount of any available goods (subject to the ship's capacity) and later sell them at a subsequent location. There is an unlimited amount of money available for purchasing. However, at no point may the total number of goods carried exceed \(k\) units.

Suppose that when buying at location \(i\) and selling at location \(j\) (with \(i<j\)), the profit per unit for a commodity is \(p_{j} - p_{i}\) (only if both buying and selling are allowed at these locations and the profit is positive). In one leg from location \(i\) to \(j\), Blue may perform transactions on up to \(k\) units (possibly different commodities) by selecting those with the highest positive profit candidates.

Your task is to determine the maximum profit Blue can obtain by the time he reaches the final location.

Input Format Outline:
The first line contains three integers \(n\), \(m\) and \(k\) representing the number of locations, the number of commodities, and the ship's capacity respectively. The following \(n\) lines each contain \(m\) integers. The \(j\)th integer on the \(i\)th line is the price of commodity \(j\) at location \(i\), or -1 if the commodity cannot be traded at that location.

Note: It is guaranteed that at each buying and selling opportunity, Blue may only perform transactions if both the buy and sell prices are available (i.e. not -1) and the difference \(p_{j} - p_{i}\) is positive. In each leg of the journey (from one location to a later location), he can perform at most \(k\) transactions (each transaction uses one unit of capacity). Transactions between different legs are disjoint since he must sell goods before making new purchases.

inputFormat

The first line contains three space-separated integers \(n\) (the number of locations), \(m\) (the number of commodity types), and \(k\) (the ship's capacity).

Then \(n\) lines follow. Each of these lines contains \(m\) space-separated integers. The \(j\)th integer of the \(i\)th line represents the price of commodity \(j\) at location \(i\) (or -1 if commodity \(j\) cannot be traded there).

outputFormat

Output a single integer representing the maximum profit Blue can achieve by the time he reaches the final location.

sample

3 2 1
3 2
5 -1
4 6

4