Maximum Flying Pigs Capture

You are given an undirected weighted simple connected graph with \(n\) nodes and \(m\) edges. Initially, at time \(0\) you are at node \(1\). Each edge is given as \((a,b,w)\) meaning that there is an edge between nodes \(a\) and \(b\) with weight \(w\). At any time \(t\), if you are at node \(v\), you can perform one of the following operations:

• Stay at node \(v\): time increases by \(1\) (i.e. move from time \(t\) to \(t+1\)).
• Travel through an edge \((a,b,w)\) with \(a=v\) or \(b=v\) and arrive at the other end; the time then increases by \(w\) (i.e. from \(t\) to \(t+w\)).

There are also \(k\) pieces of information. Each is a pair \((t_i, v_i)\) meaning that at time \(t_i\) a flying pig with id \(i\) will appear at node \(v_i\). If you are exactly at \(v_i\) at time \(t_i\), you catch the \(i\)th flying pig. Your task is to plan a route so that you catch as many flying pigs as possible.

Note: You are allowed to wait at a node until the time of an event if you arrive earlier.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) representing the number of nodes, the number of edges and the number of flying pigs respectively.

Then \(m\) lines follow, each line contains three integers \(a, b, w\) describing an edge between nodes \(a\) and \(b\) with weight \(w\).

Then \(k\) lines follow, each line contains two integers \(t_i\) and \(v_i\), meaning that at time \(t_i\) a flying pig appears at node \(v_i\).

outputFormat

Output a single integer, the maximum number of flying pigs you can catch.

sample

3 3 3
1 2 2
2 3 2
1 3 5
2 2
6 3
4 1

2