题目描述

世界上有 $N$ 个国家，编号为 $1$ 到 $N$。这些国家之间有 $M$ 条单向航线，第 $i$ 条航线从国家 $u_i$ 飞往国家 $v_i$，耗时 $t_i$ 小时。

世界上有 $K$ 种不同的护照，编号为 $1$ 到 $K$。在每个国家，对每种护照都可能有一个买入价格和一个卖出价格。某些国家可能只能买入某种护照、只能卖出某种护照，或者两者都不支持。

你最多只能额外持有一本护照。你不能卖掉自己的原始护照，但可以购买同类型的其他护照。每种护照都可以认为有无限库存。

一个盈利环定义如下：从某个国家 $x$ 出发，一开始你不持有额外护照；沿若干条航线旅行，在经过的国家中可以进行护照买卖；最后回到国家 $x$，且结束时不持有额外护照。若在回到 $x$ 时仍持有护照，只要国家 $x$ 支持卖出该护照，就可以在 $x$ 卖出。你可以任意多次经过同一个国家或同一条航线。

一个盈利环的利润为所有卖出收入减去所有买入支出。若该环的利润非负，则其效率定义为：

$$\frac{\text{profit}}{\text{time}},$$

其中 profit 是利润，time 是环的总飞行时间。没有任何买卖的环效率为 $0$。

请找出所有正时间盈利环中的最大效率，并输出其向下取整值。

输入格式

第一行包含三个整数 $N,M,K$。

接下来 $N$ 行描述各国的护照买卖价格。第 $i$ 行包含：

$$B_{i,1},S_{i,1},B_{i,2},S_{i,2},\ldots,B_{i,K},S_{i,K}.$$

其中 $B_{i,j}$ 表示在国家 $i$ 购买第 $j$ 种护照的价格，$S_{i,j}$ 表示在国家 $i$ 卖出第 $j$ 种护照的价格。

若国家 $i$ 不支持购买第 $j$ 种护照，则 $B_{i,j}=-1$；若不支持卖出，则 $S_{i,j}=-1$。

最后 $M$ 行描述航线。第 $i$ 行包含三个整数 $u_i,v_i,t_i$，表示一条从 $u_i$ 到 $v_i$、耗时 $t_i$ 小时的单向航线。

输出格式

输出一个整数，表示最大效率向下取整后的值。

数据范围

• $2 \le N \le 100$；
• $2 \le M \le 9900$；
• $2 \le K \le 1000$；
• 对所有有效买卖价格，有 $2 \le S_{i,j} \le B_{i,j} \le 10^9$；
• $1 \le t_i \le 10^7$；
• $u_i \ne v_i$；
• 任意两条航线的有序端点不同，即不存在两条相同方向的航线。

子任务

子任务	分值	附加限制	说明
1	0	无	样例
2	12	对所有 $1<i\le N,1\le j\le K$，$B_{i,j}=-1$	只能从国家 $1$ 买护照
3	21	$N,K\le 50$，且所有航线耗时均为 $1$	所有航线耗时相同
4	33	对所有可买卖项，$B_{i,j}=S_{i,j}\ne -1$	每个国家买卖同一种护照价格相同
5	34	无	无额外限制

只有通过某个子任务的全部测试，才能获得该子任务分数。

样例

输入

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

说明

考虑环 $1\to2\to3\to1$，总时间为 $3+3+1=7$。一种交易方式是：在国家 $1$ 购买护照 $2$，在国家 $2$ 卖出；随后在国家 $2$ 购买护照 $1$，最终在国家 $1$ 卖出。利润为

$$-5+15-6+9=13,$$

效率为 $13/7$，向下取整为 $1$。

考虑环 $1\to4\to3\to1$，总时间为 $1+1+1=3$。可以在国家 $1$ 购买护照 $2$，在国家 $4$ 卖出，利润为 $-5+11=6$，效率为 $6/3=2$。

因此答案为 $2$。