어둑한 방, 23시 55분경, 밀란은 세 다리 탁자에 앉아 자신의 도시에 핵 재난이 발생할 경우 일어날 수 있는 결과에 대해 생각하기 시작했습니다. 시장직을 맡고 있는 밀란은 모든 관련 사실을 매우 잘 알고 있습니다.

그는 자신의 도시에 정확히 $N$명의 사람이 살고 있으며, 각 주민은 자신의 집에 살고 있다는 것을 알고 있습니다. 정확히 $M$쌍의 집 사이에는 도로가 있으며, 각 도로를 통과하는 데 필요한 시간은 알려져 있습니다. 마지막으로, 밀란은 어느 $K$개의 집에 방공호가 있는지, 그리고 각 방공호에 몇 명의 사람을 수용할 수 있는지 알고 있습니다. 이 모든 것을 고려할 때, 밀란은 다음과 같은 질문으로 고민하고 있습니다. "모든 주민을 대피시키는 데 필요한 최소 시간은 얼마인가?" 밀란이 이 질문에 답할 수 있도록 도와주세요.

물론 대피란 모든 주민이 어떤 방공호에든 도착하는 것을 의미합니다. 이때 주민들은 최적으로(최단 경로로) 이동하며, 한 도로를 따라 여러 사람이 동시에 잠재적으로 다른 방향으로 이동할 수 있다고 가정할 수 있습니다. 또한, 주어진 도로의 부분 집합을 사용하여 모든 두 집 사이에 적어도 하나의 경로가 존재한다고 가정할 수 있습니다.

입력

첫 번째 줄에는 주민 수, 도로 수, 방공호 수를 나타내는 자연수 $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$), $K$ ($1 \le K \le 17$)가 주어집니다. 집은 $1$부터 $N$까지의 번호로 표시됩니다.

다음 $M$개의 각 줄에는 집 $A$와 $B$ ($1 \le A, B \le N, A \neq B$) 사이에 통과하는 데 $C$ ($1 \le C \le 10^9$) 단위의 시간이 걸리는 도로가 있음을 나타내는 세 자연수 $A, B, C$가 주어집니다.

다음 $K$개의 각 줄에는 번호 $X$ ($1 \le X \le N$)인 집에 최대 $Y$ ($1 \le Y \le 10^9$)명의 사람을 수용할 수 있는 방공호가 있음을 나타내는 두 자연수 $X, Y$가 주어집니다. 모든 방공호의 총 수용 인원은 $N$보다 크거나 같습니다.

출력

모든 주민을 대피시키는 데 필요한 최소 시간을 한 줄에 출력하십시오.

서브태스크

예제

입력 1

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

출력 1

3

참고

3단위 시간 동안 집 번호 1, 2, 3의 사람들은 집 1의 방공호로 갈 수 있고, 집 4와 5의 사람들은 집 4의 방공호로 갈 수 있습니다. 집 4의 방공호는 최대 2명만 수용할 수 있기 때문에 더 짧은 시간 내에는 모든 사람이 방공호에 도착할 수 없습니다.

입력 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

출력 2

5