Description

After a long trek across the vast Australian outback, you arrive alone in Cobar with a backpack. Captivated by the city’s prosperous and beautiful markets, you decide to settle down and become a merchant. Cobar has $N$ markets, numbered from $1$ to $N$, connected by $M$ directed roads. Traversing each road takes some amount of time.

There are $K$ different types of goods in Cobar, numbered from $1$ to $K$. Each market has its own prices for each good, and the buy and sell prices may differ. Not every market buys and sells every good: a market may support both buying and selling only for a subset of goods; for a particular good, a market may only buy but not sell, or only sell but not buy. If a market buys a certain good, the quantity it buys is unlimited; similarly, if a market sells a certain good, the quantity it sells is unlimited.

To gain profit more quickly, you decide to find the cycle with the highest profit efficiency. A cycle means starting from some market with an empty backpack, traveling along roads through several markets, and finally returning to the starting point. It is allowed to pass through the same market or the same road multiple times within the cycle. When passing a market, you may buy or sell goods. Once you buy a good, you must carry it in your backpack. Because your backpack is very small, you can hold at most one good at any time. When buying a good, you do not need to consider whether you have enough money; when selling, note that you can only sell the good you currently hold.

The profit gained from a cycle is the total money obtained from selling minus the total money spent on buying during the cycle. The time spent on a cycle is the sum of the traversal times of all roads along the cycle. The profit efficiency of a cycle is the profit divided by the time spent. Note that the profit efficiency of a cycle with no transactions is $0$.

You need to find, among all cycles with strictly positive total time, the maximum profit efficiency. Output the value floored to an integer. If no cycle can yield a positive profit, output $0$.

Input Format

The first line contains $3$ positive integers $N$, $M$, and $K$, denoting the number of markets, the number of roads, and the number of goods, respectively.

The next $N$ lines describe the markets. In line $i$, there are $2K$ integers $B_{i,1}, S_{i,1}, B_{i,2}, S_{i,2}, \cdots, B_{i,K}, S_{i,K}$. For any $1 \le j \le K$, the integers $B_{i,j}$ and $S_{i,j}$ denote the buying and selling price at market $i$ for good $j$, respectively. If a transaction price is $-1$, then that transaction is not available for that good at that market.

Then follow $M$ lines. In line $p$, there are $3$ integers $V_p, W_p, T_p$, indicating there is a directed road from market $V_p$ to market $W_p$ with travel time $T_p$ minutes.

Output Format

Output a single integer: the maximum profit efficiency over all cycles, floored to an integer. If no cycle can be profitable, output $0$.

4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

2

Hint

Sample explanation.

In the sample, consider the two cycles 1−2−3−1 and 1−4−3−1.

Consider the cycle 1−2−3−1: the total time is $(3+3+1)=7$ minutes. The best sequence of transactions is: at market $1$, buy good $2$ (spending $5$); at market $2$, sell good $2$ (gaining $15$), then immediately buy good $1$ (spending $6$); pass through market $3$ carrying good $1$, and upon returning to market $1$, sell it (gaining $9$). The total profit is $-5+15-6+9=13$. The profit efficiency is $\frac{13}{7}$, whose floor is $1$.

Consider the cycle 1−4−3−1: the total time is $(1+1+1)=3$ minutes. The best sequence of transactions is: at market $1$, buy good $2$ (spending $5$); at market $4$, sell good $2$ (gaining $11$); then pass through market $3$ and return to market $1$. The total profit is $-5+11=6$. The profit efficiency is $\frac 6 3$, whose floor is $2$.

Therefore, the maximum profit efficiency over all cycles is $2$.

Subtasks.

Across all testdata, the following hold: $1 \le N \le 100$, $1 \le M \le 9900$, $1 \le K \le 1000$. If in market $i$ for good $j$ both buying and selling are available, then $0 \le S_{i,j} \le B_{i,j} \le 10^9$. For road $p$ ($1 \le p \le M$), it is guaranteed that $V_p \ne W_p$ and $1 \le T_p \le 10^7$. There do not exist indices $p, q$ with $1 \le p \le q \le M$ such that $(V_p, W_p) = (V_q, W_q)$.

Translated by ChatGPT 5