In a dimly lit room, at approximately 11:55 PM, Milan sat at a three-legged table and began to think about the potential consequences that a nuclear catastrophe would cause in his city. Since Milan serves as the mayor, he is very well acquainted with all the relevant facts.

Specifically, he knows that exactly $N$ people live in his city and that each resident lives in their own house. There are roads between exactly $M$ pairs of houses, and for each road, the time required to traverse it is known. Finally, Milan knows in which $K$ houses the nuclear shelters are located and how many people each shelter can accommodate. With all this in mind, Milan is troubled by the following question: "What is the minimum time required to evacuate all the residents of this city?" Help Milan answer this question.

Of course, evacuation implies that every resident ends up in some nuclear shelter. You may assume that the residents move optimally (via the shortest path) and that multiple people can move along a single road simultaneously in potentially different directions. Also, you may assume that there is at least one path between every two houses using some subset of the given roads.

Input

The first line contains the natural numbers $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$), and $K$ ($1 \le K \le 17$), representing the number of residents, the number of roads, and the number of nuclear shelters. The houses are labeled with numbers from $1$ to $N$.

Each of the next $M$ lines contains three natural numbers $A$, $B$ ($1 \le A, B \le N, A \neq B$), and $C$ ($1 \le C \le 10^9$), indicating that there is a road between houses $A$ and $B$ that takes $C$ units of time to traverse.

Each of the next $K$ lines contains two natural numbers $X$ ($1 \le X \le N$) and $Y$ ($1 \le Y \le 10^9$), indicating that there is a nuclear shelter in house $X$ that can accommodate at most $Y$ people. The total capacity of all shelters will be greater than or equal to $N$.

Output

In the only line, print the minimum time required to evacuate all residents of this city.

Subtasks

Examples

Input 1

5 5 2
1 2 1
1 3 3
2 3 4
3 4 1
4 5 1
1 10
4 2

Output 1

3

Note

In 3 units of time, the people from houses 1, 2, and 3 can go to the shelter in house 1, and the people from houses 4 and 5 can go to the shelter in house 4. In less time, not all people can reach the shelters because the shelter in house 4 can accommodate at most two people.

Input 2

7 8 3
1 2 5
2 3 3
3 4 5
1 4 1
4 5 7
5 6 2
6 7 1
4 7 4
3 3
7 3
6 2

Output 2

5