题目描述

给定一个 $n$ 个点 $m$ 条边的边带权简单连通无向图，在 $0$ 时刻你在点 $1$ 上。

假设当前是 $t$ 时刻，你在点 $v$ 上，你可以选择两种操作：

• 仍停留在点 $v$ 上，操作后到 $t+1$ 时刻。
• 选择一条边 $(a,b,w)$ 满足 $a=v$ 或 $b=v$，则你到这条边连接的另一个点上，操作后到 $t+w$ 时刻。

有 $k$ 条信息，每一条信息形如 $(t_i,v_i)$ 表示在 $t_i$ 时刻，点 $v_i$ 上会出现一只飞猪，其编号为 $i$，若该时刻你在 $v_i$ 上，则你捕获到了 $i$ 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

输入格式

第一行为三个正整数 $n,m,k$。

接下来 $m$ 行每行三个正整数 $a_i,b_i,w_i$。

接下来 $k$ 行每行两个正整数 $t_i,v_i$。

输出格式

一行一个整数，为你能捕获到的飞猪数量的最大值。

2 1 5
1 2 2
1 2
2 2
3 2
5 1
7 2

4

提示

样例解释

最优方案如下：

$0$ 时刻，选择移动到节点 $2$，时间来到 $2$ 时刻。
$2$ 时刻，捕获到第 $2$ 只飞猪，选择停留在节点 $2$，时间来到 $3$ 时刻。
$3$ 时刻，捕获到第 $3$ 只飞猪，选择移动到节点 $1$，时间来到 $5$ 时刻。
$5$ 时刻，捕获到第 $4$ 只飞猪，选择移动到节点 $2$，时间来到 $7$ 时刻。
$7$ 时刻，捕获到第 $5$ 只飞猪。

数据范围

对于 $20\%$ 的数据，$n,m,k\le 7$。
对于 $100\%$ 的数据，$2\le n\le 200$，$1\le m\le \frac{n(n-1)}{2}$，$1\le k\le 5000$，$1\le a_i,b_i,v_i\le n$，$1\le w_i\le 1000$，$1\le t_i\le 10^9$。