在经过澳大利亚内陆的长途跋涉后，你终于抵达了伟大的科巴（Cobar）市，随身只带了一个小背包。科巴市场的奇观与美景令你着迷，你决定成为一名商人，并以科巴为家。科巴有 $N$ 个市场，编号从 $1$ 到 $N$，由 $M$ 条单向路径连接，每条路径都需要特定的时间（分钟）才能走完。

科巴的市场交易 $K$ 种不同的商品，编号从 $1$ 到 $K$。每个市场对每种商品都有固定的买入价和卖出价。并非每个市场都交易所有商品，对于给定的商品，某个市场可能只支持买入而不支持卖出，反之亦然。你可以假设每个有商品出售的市场都有无限量的该商品供应；同样，如果一个市场想要买入某种商品，它愿意无限次地重复买入。

为了尽快赚钱，你想要找到最高效的“利润循环”。利润循环是指在科巴进行的一次行程，从某个市场 $v$ 出发，此时背包为空，沿着科巴的路径穿过各个市场（途中可能买卖商品），最后回到 $v$，且背包再次为空。行程中可以多次访问同一个市场和/或多次走过同一条路径。一旦买入一件商品，必须立即放入背包；由于背包很小，在任何时候它最多只能容纳一件商品。你可以假设只要商品有货，无论你目前拥有多少钱，你总能买下它；同时，禁止卖出你未持有的商品。

此类循环获得的利润是卖出商品获得的总金额减去买入商品花费的总金额。循环的持续时间是走过其组成路径所花费的总分钟数。利润循环的效率定义为该循环获得的利润除以其持续时间。注意，不涉及任何商品买卖的利润循环效率为 $0$。

你的任务是找出所有持续时间严格为正的利润循环中效率最高的一个。你需要报告该值向下取整后的整数结果。如果不存在这样的利润循环，则报告 $0$。

输入格式

程序应从标准输入读取数据。

第一行包含 $3$ 个整数 $N$、$M$ 和 $K$：分别表示市场的数量、路径的数量和商品的数量。

接下来 $N$ 行，第 $i$ 行包含 $2K$ 个整数 $B_{i,1}, S_{i,1}, B_{i,2}, S_{i,2}, \dots, B_{i,K}, S_{i,K}$，描述一个市场。对于所有 $1 \le j \le 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$ 分钟。

输出格式

程序应输出到标准输出。

输出一个整数，即所有利润循环中最高效率向下取整后的值。

样例

样例输入 1

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

样例输出 1

2

说明 1

在样例中，我们考虑两个循环：“1 到 2 到 3 到 1”和“1 到 4 到 3 到 1”。

考虑“1 到 2 到 3 到 1”，该循环走过路径需要 $7$ 分钟。此循环中最有利可图的交易序列是在市场 1 买入商品 2（成本 5），在市场 2 卖出（利润 15），立即在市场 2 买入商品 1（成本 6），携带商品 1 经过市场 3，最后在市场 1 卖出商品 1（利润 9）。因此，在此循环中我们可以获得 $-5 + 15 - 6 + 9 = 13$ 的利润。$13/7$ 向下取整得到该循环的效率为 1。

考虑“1 到 4 到 3 到 1”，该循环走过路径需要 $3$ 分钟。此循环中最有利可图的交易序列是在市场 1 买入商品 2（成本 5），在市场 4 卖出（利润 11），然后经过市场 3 回到市场 1。因此，在此循环中我们可以获得 $-5 + 11 = 6$ 的利润。$6/3$ 向下取整得到该循环的效率为 2。

因此，科巴所有利润循环中的最高效率为 2。

子任务

对于所有子任务，$1 \le N \le 100$，$1 \le M \le 9900$，$1 \le K \le 1000$，且对于所有可买卖的商品，$0 < S_{i,j} \le B_{i,j} \le 1\,000\,000\,000$，对于所有 $1 \le i \le N$ 及 $1 \le j \le K$。此外，$V_p \neq W_p$ 且 $1 \le T_p \le 10\,000\,000$，对于所有 $1 \le p \le M$，且不存在任何边对 $1 \le p < q \le M$ 使得 $(V_p, W_p) = (V_q, W_q)$。