2308 「APIO2017」商旅

在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引，决定定居于此，做一个商人。科巴有 $N$ 个集市，集市用从 $1$ 到 $N$ 的整数编号，集市之间通过 $M$ 条 单向 道路连接，通过每条道路都需要消耗一定的时间。

在科巴的集市上，有 $K$ 种不同的商品，商品用从 $1$ 到 $K$ 的整数编号。每个集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，则它卖出这种商品的数量也是不限的。

为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许 多次 经过同一个集市或同一条道路。在经过集市时，你可以购买或者卖出商品，一旦你购买了一个商品，你需要把它装在背包里带走。由于你的背包非常小，任何时候你最多只能持有一个商品。在购买一个商品时，你不需要考虑你是否有足够的金钱，但在卖出时，需要注意只能卖出你拥有的商品。

从环路中得到的收益为在环路中卖出商品得到的金钱减去购买商品花费的金钱，而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的 盈利效率 是指从环路中得到的收益除以花费的时间。需要注意的是，一条没有任何交易的环路的盈利效率为 $0$ 。

你需要求出所有 消耗时间为正数 的环路中，盈利效率 最高 的环路的盈利效率。答案 向下取整 保留到整数。如果没有任何一条环路可以盈利，则输出 $0$ 。

第一行包含 $3$ 个正整数，$N$ , $M$ 和 $K$，分别表示集市数量、道路数量和商品种类数量。

接下来的 $N$ 行，第 $i$ 行中包含 $2K$ 个整数 $B_{i,1},S_{i,1},B_{i,2},S_{i,2},\cdots ,B_{i,K},S_{i,K}$ 描述一个集市。对于任意的 $1\leq j\leq K$ ，整数 $B_{i,j},S_{i,j}$ 分别表示在编号为 $i$ 的集市上购买、卖出编号为 $j$ 的商品时的交易价格。如果一个交易价格为 $-1$，则表示这个商品在这个集市上不能进行这种交易。

接下来 $M$ 行，第 $p$ 行包含 $3$ 个整数 $V_p,W_p,T_p$，表示存在一条从编号为 $V_p$ 的市场出发前往编号为 $W_p$ 的市场的路径花费 $T_p$ 分钟。

输出包含一个整数，表示盈利效率最高的环路盈利效率，答案 向下取整 保留到整数。如果没有任何一条环路可以盈利，则输出 $0$ 。

在样例中，我们考虑下面两条环路，1−2−3−1 和 1−4−3−1。

考虑环路 1−2−3−1：这条环路消耗的总时间是 $(3+3+1)=7$ 分钟。在这条环路中，最佳的交易方式是：在编号为 $1$ 的集市中购买编号为 $2$ 的商品（花费的金钱为 $5$）；在编号为 $2$ 的集市中卖出编号为 $2$ 的商品（得到的金钱为 $15$），然后立即购买编号为 $1$ 的商品（花费的金钱为 $6$）；带着编号为 1 的商品经过编号为 3 的集市，在回到编号为 $1$ 的城市后卖出（得到的金钱为 $9$）。在这个环路中，总盈利为 $−5+15−6+9=13$。这个环路的盈利效率为 $\frac{13}{7}$，向下取整后为 $1$ 。

考虑环路 1−4−3−1：这条环路消耗的总时间是 $(1+1+1)=3$ 分钟。在这条环路中，最佳的交易方式是：在编号为 $1$ 的集市中购买编号为 $2$ 的商品（花费的金钱为 $5$）；在编号为 $4$ 的集市中卖出编号为 $2$ 的商品（得到的金钱为 $11$）；然后经过编号为 $3$ 的集市回到编号为 $1$ 的城市。在这个环路中，总盈利为 $−5+11=6$ 。 这个环路的盈利效率为 $\frac 6 3$，向下取整后为 $2$ 。

综上所述，盈利效率最高的环路的盈利效率为 $2$。

在所有数据中，满足：$ 1\le N \le 100,1\le M \le 9900,1\le K \le 1000$，如果在编号为 $i (1\le i\le N)$ 的集市中，编号为 $j(1\le j\le K)$ 的商品既可以购买又可以卖出，则 $0\le S_{ij}\le B_{ij}\le 10^9$​。

对于编号为 $p (1\le p\le M)$ 的道路，保证 $V_p\neq W_p$，且 $1\le T_p\le 10^7$。

不存在满足 $1\le p\le q\le M$ 的 $p,q$ 使得 $(V_p,W_p)=(V_q,W_q)$。

详细子任务如下表：