Jamal 拥有一家新的网约车公司。他的公司运营方式如下：在乘客希望乘车前至少 12 小时，客户会预订从起点到终点的行程，并指定出发时间。尽管 Jamal 过去曾考虑过拼车，但由于疫情持续，目前每笔预订的行程在开始下一笔行程前都会先完成。Jamal 的公司拥有当前服务区域的布局图，以及行驶每条特定道路所需时间的上限。在某些时候，团队希望结合交通数据使地图动态化，但目前我们只能使用固定的成本数据。

通过提前安排每次行程，Jamal 的公司能够优化路线规划，并为司机提供一种有吸引力的商业模式。他的公司做法如下：每 8 小时，Jamal 会选择一组司机来完成一个轮班，根据客户期望的时间表接送乘客。司机按轮班获得报酬，而不是按完成的行程数量计费。Jamal 发现，与当前的网约车公司相比，这种模式对司机来说更令人满意。在当前的公司中，司机面临着无法确定能接到多少订单的风险，从而无法确定能赚多少钱。而 Jamal 的公司则为司机工作的每个轮班支付报酬，因此司机要么在赚钱（如果他们工作），要么可以自由支配时间（如果他们不需要轮班），而不是坐在车里等待乘客叫车。

不幸的是，Jamal 更擅长商业经营，在公司编程方面需要帮助。具体来说，给定一个 8 小时窗口内的一组预订行程，他缺乏一种算法来确定该轮班所需雇佣的最少司机数量。你能帮 Jamal 完成这项关键任务吗？

图 1. 样例输入示意图。虚线红色箭头表示预订的行程及其各自的开始时间。最优解是让一名司机在时间 0 完成从 2 到 3 的行程，然后行驶到位置 1 并于时间 8 到达，接着完成从 1 到 2 的行程。第二名司机可以完成从 3 到 4 的行程。

输入格式

输入的第一行包含三个整数：$n$ ($2 \le n \le 100$)，表示服务区域模型中的接送点数量；$m$ ($1 \le m \le n \times (n - 1)$)，表示服务区域内单向道路的数量；$k$ ($1 \le k \le 1000$)，表示必须完成的预订行程数量。接下来的 $m$ 行，每行包含三个整数 $u, v$ 和 $w$ ($1 \le u, v \le n, u \neq v, 1 \le w < 480$)，表示存在一条从位置 $u$ 到位置 $v$ 的道路，行驶需要 $w$ 分钟。在任意两个位置 $u$ 和 $v$ 之间，可能存在从 $u$ 到 $v$ 以及从 $v$ 到 $u$ 的道路，但任意两个位置之间在同一方向上最多只有一条道路。接下来的 $k$ 行，每行包含三个整数 $u, v$ 和 $t$ ($1 \le u, v \le n, u \neq v, 0 \le t < 480$)，表示有一个从位置 $u$ 到位置 $v$ 的行程请求，于第 $t$ 分钟从位置 $u$ 出发。同一出发位置在同一时间，或同一到达位置在同一时间，可能会有多个行程请求。保证任意位置均可从其他任何位置到达。

输出格式

输出一个整数，表示为完成所有行程该轮班必须雇佣的最少司机数量。道路可供任意数量的司机同时使用。假设接送乘客耗时为 0 分钟。在同一地点接送乘客不会延误行程。假设受雇司机可以行驶到任何起始位置，以便在第 0 分钟准备好接取任何行程，并且愿意完成在第 480 分钟之前请求、但在第 480 分钟或之后结束的行程。客户必须在他们期望的出发时间被准时接走。

样例

输入 1

4 5 3
1 2 3
2 3 6
3 1 2
3 4 8
4 3 9
1 2 8
2 3 0
3 4 5

输出 1

2