Travelling Merchant

After a long journey through the Australian outback, you arrive in the city of Cobar with nothing but a small backpack. Fascinated by the energy of its markets, you decide to settle there as a merchant. Cobar has $N$ markets numbered from $1$ to $N$, connected by $M$ one-way footpaths, where walking along each path takes a given number of minutes.

The markets trade $K$ different items numbered from $1$ to $K$. Each market sets a buying price and a selling price for each item. Not every market handles every item, and for a given item a market may support only buying or only selling. Assume that a market offering an item for sale has an unlimited supply, and that a market willing to buy an item keeps buying it without limit.

To earn money as quickly as possible, you want the most efficient profit cycle. A profit cycle is a walk that starts at some market $v$ with an empty backpack, follows footpaths while optionally buying and selling items, and returns to $v$ with an empty backpack. It may pass through the same market or footpath many times. A bought item must go into the backpack at once, and the backpack holds at most one item at any time. Assume you can always buy an available item regardless of how much money you hold, and that you cannot sell an item you do not hold.

The profit of a cycle is the total money received from sales minus the total money spent on purchases. Its duration is the sum of walking minutes along its footpaths. Its efficiency is profit divided by duration. A cycle with no trades has efficiency $0$.

Among all profit cycles with strictly positive duration, find the maximum efficiency, rounded down to an integer. If no such cycle exists, report $0$.

Your program should read from standard input.

The first line contains three integers $N$, $M$ and $K$, the numbers of markets, footpaths and items.

Then $N$ lines follow. The $i$th of these lines contains $2K$ integers $B_{i,1}, S_{i,1}, B_{i,2}, S_{i,2}, \dots, B_{i,K}, S_{i,K}$ describing a market. For every $1 \le j \le K$, the pair $B_{i,j}$ and $S_{i,j}$ are the prices at which you can buy and sell item $j$ at market $i$. If an item cannot be bought or sold, $-1$ is used as a placeholder.

Then $M$ lines follow. The $p$th of these lines contains three integers $V_p$, $W_p$ and $T_p$, describing a one-way footpath from market $V_p$ to market $W_p$ that takes $T_p$ minutes.

Your program should write to standard output.

Print a single integer, the maximum efficiency among all profit cycles, rounded down to the nearest integer.

For all subtasks, $1 \le N \le 100$, $1 \le M \le 9900$ and $1 \le K \le 1000$. For every item that can be bought or sold, $0 < S_{i,j} \le B_{i,j} \le 1000000000$ for all $1 \le i \le N$ and all $1 \le j \le K$. In addition, $V_p \ne W_p$ and $1 \le T_p \le 10000000$ for all $1 \le p \le M$, and there is no pair of paths $1 \le p < q \le M$ with $(V_p, W_p)$ equal to $(V_q, W_q)$. That is, no directed pair of markets appears twice.

In the sample case there are two cycles to consider, one returning from $1$ through $2$ and $3$ to $1$, and one returning from $1$ through $4$ and $3$ to $1$.

The first cycle takes $3 + 3 + 1 = 7$ minutes to walk. Its most profitable sequence of trades is to buy item $2$ at market $1$, sell it at market $2$, then buy item $1$ at market $2$, carry it through market $3$, and finally sell it at market $1$. The profit is $-5 + 15 - 6 + 9 = 13$, and $13/7$ rounded down gives efficiency $1$.

The second cycle takes $1 + 1 + 1 = 3$ minutes to walk. Its most profitable sequence of trades is to buy item $2$ at market $1$, sell it at market $4$, and then pass through market $3$ back to market $1$. The profit is $-5 + 11 = 6$, and $6/3 = 2$, so the efficiency is $2$.

Therefore the best efficiency of any profit cycle is $2$.